fork(1) download
  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<map>
  6.  
  7. #define left (2*idx+1)
  8. #define right (2*idx+2)
  9.  
  10. using namespace std;
  11.  
  12. const int SZ = 200;
  13. const int SEG_SZ = 4*SZ;
  14. int SEG[SEG_SZ];
  15. int LAZY[SEG_SZ];
  16.  
  17. inline void clear_lazy(int idx, int s, int e) {
  18. if (LAZY[idx]) {
  19. SEG[idx] += LAZY[idx];
  20. if (s != e) {
  21. LAZY[left] += LAZY[idx];
  22. LAZY[right] += LAZY[idx];
  23. }
  24. LAZY[idx] = 0;
  25. }
  26. }
  27.  
  28. void update(int idx, int rs, int re, int ent, int ex) {
  29. clear_lazy(idx, rs, re);
  30. if (ent > re || ex < rs) return;
  31. if (ent <= rs && ex >= re) {
  32. SEG[idx]++;
  33. LAZY[left]++;
  34. LAZY[right]++;
  35. } else {
  36. int mid = (rs + re)/2;
  37. update(left, rs, mid, ent, ex);
  38. update(right, mid+1, re, ent, ex);
  39. SEG[idx] = max(SEG[left], SEG[right]);
  40. }
  41. }
  42.  
  43. int main() {
  44. int arr[200], index[200];
  45. int t;
  46. cin >> t;
  47. for (int i=0; i<t; i++) {
  48. memset(SEG, 0, sizeof(SEG));
  49. memset(LAZY, 0, sizeof(LAZY));
  50. int q;
  51. cin >> q;
  52. for (int i=0; i<q; i++) {
  53. cin >> arr[2*i];
  54. cin >> arr[2*i+1];
  55. index[2*i] = 2*i;
  56. index[2*i+1] = 2*i+1;
  57. }
  58. sort(index, index+2*q, [&arr](int a, int b) -> bool {
  59. return arr[a] < arr[b];
  60. });
  61. map<int, int> m;
  62. for (int i=0; i<2*q; i++) {
  63. m[arr[index[i]]] = i;
  64. }
  65. for (int i=0; i<2*q; i++) {
  66. arr[i] = m[arr[i]];
  67. }
  68. for (int i=0; i<2*q; i+=2) {
  69. update(0, 0, SZ-1, arr[i], arr[i+1]-1);
  70. }
  71. cout << SEG[0] << endl;
  72. }
  73. return 0;
  74. }
  75.  
Success #stdin #stdout 0s 4712KB
stdin
1
100
5836921 8013599
43317 8997343
7471825 9120321
9457585 9970753
3357386 4798971
3602927 5241405
4084254 8931458
5128781 5629039
621884 793827
2915040 6349408
8805231 9650895
7021766 8661862
3491859 7957433
558438 9898775
7294653 9502896
7459774 9096049
4814783 8236625
5802150 9104621
7155354 8528251
620742 7754460
457223 9900497
7390807 9732825
83690 8352129
845696 4299362
7638301 9203171
5385942 7136405
1316278 1605229
1129843 3934296
9029885 9195142
9169383 9704143
9719275 9991786
5959741 6138369
1535017 7484070
8877825 9363018
9851521 9920016
2514888 4759118
7537722 7593174
2756316 3006473
5585204 5825493
9936647 9983807
8883697 9450235
7239827 7921274
7943124 8996074
8036456 9773574
2957251 8838009
6024842 7863841
8571019 9127076
7141656 9446464
903342 9566763
8654052 8837010
4406676 8948435
3849759 8737614
4215280 7802169
394372 2515210
3540861 9323151
3808679 8863317
5419760 7265207
6367728 9784271
6475739 9836000
2415250 7469514
9229908 9706226
8244193 9830929
7793239 9216327
8404051 8966983
3905954 9914144
8302839 8513891
4012118 6825541
4661815 6750527
7909954 8663490
9633351 9954294
8278669 9859552
6817061 6993755
5958130 9696966
7431611 9429445
9702284 9845844
2765175 7197617
2350565 7050448
786637 1240941
2721701 2958372
1654331 7039050
4707291 5333760
8889828 9478941
3606011 8633624
4056992 5458542
266250 1612531
6447428 6572980
8413334 9380351
6813247 9343534
2687153 6177834
7382298 8308033
951904 3062370
2015666 8653632
8760859 9155083
2249677 3497337
4963199 4965595
3109505 7786221
7179099 7455890
4089470 8525472
7675913 8185229
3679391 7982240
stdout
41