fork download
copy 
  1. #include <cstdio>
  2. #include <cassert>
  3. using namespace std;
  4. #define MAXN 1000000
  5. #define MAXM 1000000
  6. #define MAXQ 1000000
  7. int N, M, Q, L, R, X;
  8. int start[MAXN+1];
  9. int end[MAXN+1];
  10. int days[MAXN+1];
  11. int ans[MAXN+1];
  12. void solve(){
  13. 	int count = 0;
  14. 	for(int i=0;i<=MAXN;i++){
  15. 		count = count + start[i];
  16. 		days[i] = count;
  17. 		count = count - end[i];
  18. 	}
  19. 	for(int i=0;i<=MAXN;i++)
  20. 		ans[days[i]]++;
  21. 	for(int i=MAXN-1;i>0;i--)
  22. 		ans[i] += ans[i+1];
  23. 	return;
  24. }
  25. void init(){
  26. 	for(int i=0;i<=MAXN;i++)
  27. 		start[i] = end[i] = ans[i] = 0;
  28. }
  29. int main(){
  30. 	init();
  31. 	scanf("%d", &N);
  32. 	assert(N>0 and N<=MAXN);
  33. 	scanf("%d", &M);
  34. 	assert(M>0 and M<=MAXM);
  35. 	for(int i=0;i<M;i++){
  36. 		scanf("%d %d", &L, &R);
  37. 		assert(L>0 and L<=N);
  38. 		assert(R>0 and R<=N);
  39. 		assert(L<=R);
  40. 		start[L]++;
  41. 		end[R]++;
  42. 	}
  43. 	solve();
  44. 	scanf("%d", &Q);
  45. 	assert(Q>0 and Q<=MAXQ);
  46. 	while(Q--){
  47. 		scanf("%d", &X);
  48. 		assert(X>0 and X<=N);
  49. 		printf("%d\n", ans[X]);
  50. 	}
  51. 	return 0;
  52. }
Success #stdin #stdout 0.02s 19088KB
comments (?)
stdin
copy 
7
4
1 3
2 5
1 2
5 6
4
1
7
4
2
stdout
copy 
6
0
0
4
https://ideone.com/qbQ0KX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!