fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=1e5+5;
  19. int n,m,w,h,sz;
  20. struct Event
  21. {
  22.     int pos,type,bot,top;
  23. };
  24. vector<Event> event;
  25. bool cmp(const Event &x, const Event &y)
  26. {
  27.     return x.pos<y.pos;
  28. }
  29. vector<int> v;
  30. void pre()
  31. {
  32.     sort(v.begin(),v.end());
  33.     v.erase(unique(v.begin(),v.end()),v.end());
  34.     m=v.size();
  35.     sort(event.begin(),event.end(),cmp);
  36.     sz=event.size()-1;
  37. }
  38. int getVal(int x)
  39. {
  40.     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
  41. }
  42.  
  43. int st[4*MAX],lazy[4*MAX];
  44. void push_down(int u, int l, int r)
  45. {
  46.     if(lazy[u]==0) return;
  47.     st[u]+=lazy[u];
  48.     if(l!=r)
  49.     {
  50.         lazy[u<<1]+=lazy[u];
  51.         lazy[(u<<1)|1]+=lazy[u];
  52.     }
  53.     lazy[u]=0;
  54. }
  55. void update(int u, int l, int r, int ul, int ur, int val)
  56. {
  57.     push_down(u,l,r);
  58.     if(r<ul || l>ur) return;
  59.     if(ul<=l && r<=ur)
  60.     {
  61.         st[u]+=val;
  62.         if(l!=r)
  63.         {
  64.             lazy[u<<1]+=val;
  65.             lazy[(u<<1)|1]+=val;
  66.         }
  67.         return;
  68.     }
  69.     int mid=(l+r)>>1;
  70.     update(u<<1,l,mid,ul,ur,val); update((u<<1)|1,mid+1,r,ul,ur,val);
  71.     st[u]=max(st[u<<1],st[(u<<1)|1]);
  72. }
  73. int query(int u, int l, int r, int ql, int qr)
  74. {
  75.     if(ql>qr) return 0;
  76.     push_down(u,l,r);
  77.     if(ql<=l && r<=qr) return st[u];
  78.     int mid=(l+r)>>1;
  79.     if(qr<=mid) return query(u<<1,l,mid,ql,qr);
  80.     if(ql>mid) return query((u<<1)|1,mid+1,r,ql,qr);
  81.     return max(query(u<<1,l,mid,ql,qr),query((u<<1)|1,mid+1,r,ql,qr));
  82. }
  83.  
  84.  
  85. void calc()
  86. {
  87.     int ans=0,i=0;
  88.     while(i<sz)
  89.     {
  90.         int curPos=event[i].pos;
  91.         while(i<sz && event[i].pos==curPos)
  92.         {
  93.             int ul=getVal(event[i].bot), ur=getVal(event[i].top);
  94.             update(1,1,m,ul,ur,event[i].type);
  95.             ++i;
  96.         }
  97.         int tmp=query(1,1,m,1,m);
  98.         ans=max(ans,tmp);
  99.     }
  100.     cout<<ans;
  101. }
  102.  
  103. int main()
  104. {
  105.     fastio
  106.  
  107.     if(fopen(FILE ".inp","r"))
  108.     {
  109.         freopen(FILE ".inp","r",stdin);
  110.         freopen(FILE ".out","w",stdout);
  111.     }
  112.  
  113.     cin>>n>>w>>h;
  114.     v.pb(0);
  115.     foru(i,1,n)
  116.     {
  117.         int x,y; cin>>x>>y;
  118.         v.pb(y); 
  119.         if(y>h) v.pb(y-h);
  120.         int l=max(0,x-w), r=x, bot=max(0,y-h), top=y;
  121.         event.pb({l,1,bot,top}); event.pb({r+1,-1,bot,top});
  122.     }
  123.     pre();
  124.     calc();
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VqfM5t
language:
C++14 (gcc 8.3)
created:
9 hours 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!