fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <memory.h>
  4. #include <time.h>
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <functional>
  8. #include <set>
  9. #include <map>
  10. #include <string>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <fstream>
  14. #include <stack>
  15. #include <queue>
  16. #include <vector>
  17. #include <iomanip>
  18. #include <iostream>
  19. #include <assert.h>
  20.  
  21. #define ALL(x) x.begin(), x.end()
  22. #define fill(a) memset(a, 0, sizeof(a))
  23. #define abs(x) ((x)>0?(x):-(x))
  24. #define sqr(x) (1ll*(x)*(x))
  25. #define min(a,b) ((a)>(b)?(b):(a))
  26. #define max(a,b) ((a)<(b)?(b):(a))
  27. #define gcd(a,b) __gcd(a,b)
  28. #define F first
  29. #define S second
  30. #define SS stringstream
  31. #define CC(x) cout << x << endl
  32. #define CCS(x) cout << x << " "
  33. #define pw(x) (1ll<<(x))
  34. #define pb push_back
  35. #define mp make_pair
  36. #define FIN freopen("1.in", "r", stdin)
  37. #define FOUT freopen("1.out", "w", stdout)
  38. #define FILE FIN; FOUT
  39. #define SC(x) scanf("%d", &x)
  40. #define PR(x) printf("%d\n", x)
  41. #define PRS(x) printf("%d ", x)
  42. #define pii pair<int,int>
  43. #define vi vector<int>
  44. #define vii vector<pair<int,int> > 
  45. #define forr(i, l, r) for (int i = l; i <= r; i++)
  46. #define SRD srand((int)time(NULL))
  47. #define GC getchar()
  48.  
  49. typedef long long LL;
  50. typedef unsigned long long ULL;
  51. typedef double DD;
  52. typedef long double LD;
  53. typedef unsigned char UC;
  54. typedef unsigned int UI;
  55. typedef unsigned short US;
  56.  
  57. using namespace std;
  58.  
  59. #define N 111111
  60.  
  61. int n, sss[N], ans = 0;
  62. pair<int, pii > a[N];
  63. set <int> s;
  64. set <int> :: iterator it;
  65. vi er;
  66.  
  67.         inline int fs(int x)
  68.         {
  69.                 int res = 0;
  70.                 for(int j = x; j >= 0; j = (j&(j+1))-1) res += sss[j];
  71.                 return res;
  72.         }
  73.  
  74.         inline void upd(int x)
  75.         {
  76.                 for(int j = x; j<=50050; j |= j+1) sss[j]++;
  77.         }
  78.  
  79. int main(int argc, char * argv[])
  80. {
  81.         //ios_base::sync_with_stdio(0);
  82.         //FIN;
  83.         SC(n);
  84.         forr(i, 1, n)
  85.         {
  86.                 int x, y, z;
  87.                 SC(x); SC(y); SC(z);
  88.                 a[i] = mp(y, mp(x, z));
  89.         }
  90.         sort(a+1, a+n+1);
  91.         forr(i, 0, 50001) s.insert(i);
  92.         forr(i, 1, n)
  93.         {
  94.                 int r = a[i].F, l = a[i].S.F, c = a[i].S.S;
  95.                 int sum = fs(r)-fs(l-1);
  96.                 if (sum >= c) continue;
  97.                 it = s.lower_bound(r);
  98.                 if (it == s.end() || *it != r) it--;
  99.                 er.clear();
  100.                 for(;;)
  101.                 {
  102.                         if (sum == c) break;
  103.                         sum++;
  104.                         upd(*it);
  105.                         ans++;
  106.                         er.pb(*it);
  107.                         it--;
  108.                 }
  109.                 for(int j = 0; j<er.size(); j++) s.erase(er[j]);
  110.         }
  111.         CC(ans);
  112.         return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 6272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NMYH6F
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!