fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define int long long
  6. #define pb push_back
  7. #define f first
  8. #define s second
  9. #define pq priority_queue
  10. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  11. #define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  12.  
  13. using namespace std;
  14.  
  15. // #include <ext/pb_ds/assoc_container.hpp>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // using namespace __gnu_pbds;
  18.  
  19. // template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. // template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  21.  
  22. const int N=2e5+10;
  23. map<int, int> comp;
  24. int uncomp[N];
  25. int nexti[N];
  26.  
  27. struct segTree{
  28.     vector<int> maxi, lazy, allowed;
  29.     int n;
  30.     void init(int n2){
  31.         n=1; while(n<n2) n*=2;
  32.         maxi.assign(4*n, 0);
  33.         lazy.assign(4*n, 0);
  34.         allowed.assign(4*n, 0);
  35.     }
  36.  
  37.     void prop(int c){
  38.         lazy[2*c+1]+=lazy[c];
  39.         lazy[2*c+2]+=lazy[c];
  40.         maxi[c]+=lazy[c];
  41.  
  42.         lazy[c]=0;
  43.     }
  44.  
  45.     int getCell(int c, int lc, int rc){
  46.         return (lc+1==rc?(allowed[c]>0?maxi[c]:0):maxi[c]);
  47.     }
  48.  
  49.     void set(int i, int val, int c, int lc, int rc){
  50.         prop(c);
  51.         if(lc+1==rc){allowed[c]=val; return;}
  52.  
  53.         int m=(lc+rc)/2;
  54.         if(i<m) set(i, val, 2*c+1, lc, m);
  55.         else set(i, val, 2*c+2, m, rc);
  56.  
  57.         prop(2*c+1); prop(2*c+2);
  58.  
  59.         maxi[c]=max(getCell(2*c+1, lc, m), getCell(2*c+2, m, rc));
  60.     }
  61.     void set(int i, int val){
  62.         set(i, val, 0, 0, n);
  63.     }
  64.  
  65.     void increase(int l, int r, int val, int c, int lc, int rc){
  66.         if(lc>=l&&rc<=r){
  67.             lazy[c]+=val;
  68.             prop(c);
  69.             return;
  70.         }
  71.         prop(c);
  72.         if(lc>=r||rc<=l) return;
  73.  
  74.         int m=(lc+rc)/2;
  75.         increase(l, r, val, 2*c+1, lc, m); increase(l, r, val, 2*c+2, m, rc);
  76.  
  77.         maxi[c]=max(getCell(2*c+1, lc, m), getCell(2*c+2, m, rc));
  78.     }
  79.     void increase(int l, int r, int val){
  80.         increase(l, r, val, 0, 0, n);
  81.     }
  82. };
  83.  
  84. void solve(){
  85.     int n, m, k; cin>>n>>m>>k;
  86.     vector<pair<int, int>> v1(m);
  87.     for(int i=0; i<m; i++) cin>>v1[i].f>>v1[i].s;
  88.  
  89.     sort(v1.begin(), v1.end());
  90.  
  91.     vector<int> ys; for(int i=0; i<m; i++) ys.pb(v1[i].s);
  92.     sort(ys.begin(), ys.end());
  93.  
  94.     int cntr=0;
  95.     for(int i=0; i<m; i++){
  96.         if(comp.count(ys[i])) continue;
  97.         comp[ys[i]]=cntr;
  98.         uncomp[cntr]=ys[i];
  99.  
  100.         cntr++;
  101.     }
  102.  
  103.     for(int i=cntr; i<N; i++) uncomp[i]=2e9;
  104.  
  105.     for(int i=0; i<cntr; i++){
  106.         int ind=upper_bound(uncomp+i, uncomp+N, uncomp[i]+k-1)-uncomp;
  107.         nexti[i]=ind;
  108.     }
  109.     comp[2e9]=m;
  110.  
  111.     segTree seg1; seg1.init(m);
  112.     int ans=0;
  113.     int l=0;
  114.     for(int i=0; i<m; i++){
  115.         while(l<i&&v1[l].f<=v1[i].f-k){
  116.             seg1.increase(comp[v1[l].s], nexti[comp[v1[l].s]], -1);
  117.             seg1.set(comp[v1[l].s], -1);
  118.             l++;
  119.         }
  120.         seg1.increase(comp[v1[i].s], nexti[comp[v1[i].s]], 1);
  121.         seg1.set(comp[v1[i].s], 1);
  122.  
  123.         ans=max(ans, seg1.maxi[0]);
  124.     }
  125.     cout<<ans<<endl;
  126. }
  127.  
  128. int32_t main() {
  129.     #ifndef ONLINE_JUDGE
  130.         read_file;
  131.     #endif
  132.  
  133.     fast;
  134.  
  135.     int t;
  136.     t=1;
  137.     // cin>>t;
  138.     while(t--){
  139.         solve();
  140.     }
  141.     return 0;
  142. }
Success #stdin #stdout 0.01s 6352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/o1fmaX
language:
C++14 (gcc 8.3)
created:
24 days 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!