Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int baza = (1<<4);
  7.  
  8. long long drzewo[baza];
  9. long long nwm[baza];
  10.  
  11. void push(int v){
  12. nwm[v*2]+=nwm[v];
  13. drzewo[v*2]+=nwm[v];
  14. nwm[v*2+1]+=nwm[v];
  15. drzewo[v*2+1]+=nwm[v];
  16. nwm[v]=0;
  17.  
  18. return;
  19. }
  20.  
  21. void update(int v){
  22. drzewo[v]=max(drzewo[v*2],drzewo[v*2+1]);
  23.  
  24. return;
  25. }
  26.  
  27.  
  28.  
  29. void add(int a,int b,int c, int v=1,int l=1,int r=baza){
  30. if(l>b||r<a){
  31. return;
  32. }
  33. if(l>=a&&r<=b){
  34. drzewo[v]+=c;
  35. nwm[v]+=c;
  36. return;
  37. }
  38. push(v);
  39. int s=(l+r)/2;
  40. add(a,b,c,2*v,l,s);
  41. add(a,b,c,2*v+1,s+1,r);
  42. update(v);
  43.  
  44. return;
  45. }
  46.  
  47.  
  48. int main()
  49. {
  50. int s,w;
  51. int n;
  52. int x,y;
  53. vector <int> tabx[60002]={};
  54. cin>>s>>w>>n;
  55. for(int i=0;i<n;i++){
  56. cin>>x>>y;
  57. //x+=30001;
  58. //y+=30001;
  59. x+=1;
  60. y+=1;
  61. tabx[x].push_back(y);
  62. }
  63. long long mm=0;
  64. for(int i=0;i<60002;i++){
  65. if(i>=s){
  66. for(int j=0;j<tabx[i-s].size();j++){
  67. add(tabx[i-s][j],tabx[i-s][j]+w,-1);
  68. }
  69. }
  70. for(int j=0;j<tabx[i].size();j++){
  71. add(tabx[i][j],tabx[i][j]+w,1);
  72. cout<<drzewo[1]<<endl;
  73. }
  74. mm=max(mm,drzewo[1]);
  75. }
  76. cout<<mm;
  77.  
  78.  
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement