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.|

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);
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.