Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PBCSEQ - Các đoạn nguyên

Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.

Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.

Kết quả

Một số duy nhất là kết quả của bài toán.

Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000

Ví dụ

Dữ liệu

3

1 6

2 5

3 4 Kết quả

3

Dữ liệu

6

1 4

1 5

1 6

1 7

2 5

3 5 Kết quả

5

Chú ý: O(N^2) ăn được 50% số test.

Được gửi lên bởi:bnta2
Ngày:2008-06-14
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatia open contest 07-08

hide comments
2012-03-09 05:01:40 KHD
:(((

Last edit: 2012-04-16 09:33:01
2012-01-10 07:32:33 Xi Ke
Ai AC bài này rồi cho mình xin 1 số bộ test được không.
2011-10-10 15:15:14 Yên Vũ
quicksort O(nlogn), tìm dãy con O(nlogn) ~> O(nlogn) chứ nhỉ?

Last edit: 2011-10-11 08:57:37
2011-09-23 06:08:00 Ðỗ Quốc Bảo
Mình có ý tưởng thế này:
đầu tiên sắp xếp quick sort giảm dần
sau đó tìm dãy con giảm dài nhất, nhớ xét điều kiện đầu và cuối của đoạn.
làm O(n^2), 50 điểm... chán
2011-06-23 00:46:07 Angel
Sao cái bộ 2 kia lại ra 5 nhỉ? nếu 1-4 nằm trong 1-7 thì phải lấy được cả 6 còn nếu không thì chỉ lấy được tối đa 3 thôi chứ nhỉ. >"<
2011-03-16 17:03:04 trandatbav
Ai co chut y tuong bai nay ko a
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.