| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT125C - Dãy số 3 |
Cho dãy số N (1 <= N <= 1,000,000, N lẻ) phần tử đánh số từ 1 đến N, ban đầu có giá trị là 0. Có tất cả K (1<=K<=25,000) truy vấn, mỗi truy vấn có dạng "A B" sẽ thực hiện tăng các phần tử trong đoạn [A,B] lên một đơn vị.
Sau khi thực hiện K truy vấn, tìm giá trị phần tử trung vị (phần tử ở chính giữa nếu sắp xếp dãy tăng dần) của dãy.
Input
- Dòng 1: N và K
- Dòng 2..K+1: Mỗi dòng chứa 1 truy vấn có dạng "A B" (1<=A,B<=N) có ý nghĩa như trong đề bài.
Output
Giá trị phần tử trung vị của dãy sau khi hiện K truy vấn.
Example
Input: 7 4
5 5
2 4
4 6
3 5
Output: 1
Giải thích:
Sau khi thực hiện các truy vấn dãy trở thành 0,1,2,3,3,1,0.
Sắp xếp lại thành 0,0,1,1,2,3,3.
| Được gửi lên bởi: | adm |
| Ngày: | 2012-03-12 |
| Thời gian chạy: | 0.100s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2018-02-26 17:19:37
PTIT125C: https://e16cn-ptit.blogspot.com/2018/02/ptit125c-day-so-3.html |
|
|
2017-04-03 11:13:18
c bị tràn mảng nhé khai báo s có nhiều phần tử hơn đi |
|
|
2015-06-27 07:49:27 TICHPX
Điên đẩu cà cuối cùng cũng AC với thuật toán O(n) |
|
|
2015-04-03 14:03:11 Fake
sort vector cũng TLE the có cách gì chăng |
|
|
2014-11-28 21:08:23 X-Dante
25k truy vấn * max [A,B] ~ 10^9 >>> TLE |
|
|
2014-09-29 11:56:01 Cường D14AT1
Thuật toán mình độ phức tạp O(nlog2N) do có quicksort và TLE :(,xử lí truy vấn độ phức tạp O(n) Last edit: 2014-09-29 11:56:36 |
|
|
2014-07-24 18:29:03 Flappybird
[Help] Minh toàn bị báo là "chạy bị lỗi(SIGSEGV)" :( #include<stdio.h> int main(){ long s[1000]={0},n,k,z; scanf("%ld %ld",&n,&k); long a,b; for(long i=0;i<k;i++){ scanf("%ld %ld",&a,&b); for(long j=a-1;j<=b-1;j++) s[j]=s[j]+1; } for(long i=0;i<n-1;i++) for(long j=i+1;j<n;j++){ if(s[i]>s[j]) {z=s[j];s[j]=s[i];s[i]=z;} } printf("%ld",s[(n-1)/2]); return (0); } |
