Guest User

Untitled

a guest
Jun 26th, 2017
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int tree[4000000];
  9.  
  10. inline void update(int node,int i,int j,int pos) {
  11.    
  12.     if(pos<i || pos>j) return;
  13.    
  14.     if(i==j) {
  15.         tree[node]++;
  16.         return;
  17.     }
  18.    
  19.     update(node<<1,i,(i+j)>>1,pos);
  20.     update((node<<1)+1,((i+j)>>1)+1,j,pos );
  21.    
  22.     tree[node]=tree[node<<1]+tree[(node<<1)+1];
  23. }
  24.  
  25. inline int query(int node,int x,int y,int i,int j) {
  26.    
  27.     if(j<x || i>y)
  28.         return 0;
  29.    
  30.     if(x>=i && y<=j)
  31.         return tree[node];
  32.    
  33.     return query(node<<1,x,(x+y)>>1,i,j)+query((node<<1)+1,((x+y)>>1)+1,y,i,j);
  34. }
  35.  
  36. struct my_event
  37. {
  38.     bool type;
  39.     int pos;
  40.     int val;
  41.     int a,b;
  42.     // int c;
  43. } S[200001];
  44.  
  45. //type: 0->numberEvent , 1->queryEvent
  46. bool operator < (const my_event &X,const my_event &Y)
  47. {
  48.    
  49.     if(X.type==Y.type)
  50.         return X.val>Y.val;
  51.    
  52.     if(X.type == 0 && Y.type == 1) {
  53.         return X.val >= Y.val;
  54.     }
  55.     if(X.type == 1 && Y.type == 0) {
  56.         return X.val > Y.val;
  57.     }
  58.     return false;
  59. }
  60.  
  61. int result[100001];
  62.  
  63. int n;
  64. int arr[100001];
  65. bool solved[100001];
  66. int startOfGroup[100001];
  67. int endOfGroup[100001];
  68. int groupSize[100001];
  69.  
  70. void precompute() {
  71.    
  72.     int leftEnd = -1;
  73.     int counter=1;
  74.     for(int i = 1; i <= n; i++) {
  75.        
  76.         if(i == 1 || arr[i] != arr[i-1]) {
  77.             leftEnd = i;
  78.             if(i > 1) {
  79.                 groupSize[i-1] = counter;
  80.             }
  81.             counter = 0;
  82.            
  83.         }
  84.        
  85.         counter++;
  86.         startOfGroup[i] = leftEnd;
  87.         if(i == n) {
  88.             groupSize[n] = counter;
  89.         }
  90.     }
  91.    
  92.     int rightEnd = -1;
  93.     for(int i = n; i >= 1; i--) {
  94.         if(i == n || arr[i] != arr[i+1]) {
  95.             rightEnd = i;
  96.         }
  97.         endOfGroup[i] = rightEnd;
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     int t;
  104.  
  105.     cin >> t;
  106.    
  107.     while(t--) {
  108.         memset(tree,0,sizeof(tree));
  109.         memset(result,0,sizeof(result));
  110.         memset(solved,false,sizeof(solved));
  111.         memset(startOfGroup,0,sizeof(startOfGroup));
  112.         memset(endOfGroup,0,sizeof(endOfGroup));
  113.         memset(groupSize,0,sizeof(groupSize));
  114.         int events=0;
  115.        
  116.         int i,c,q;
  117.         int a,b;
  118.        
  119.        
  120.         cin >> n >> q;
  121.        
  122.         for(int i = 1; i <= n; i++) {
  123.             cin >> arr[i];
  124.         }
  125.        
  126.         precompute();
  127.        
  128.         for(i=1;i<=n;i++) {
  129.             if(groupSize[i] > 0) {
  130.                 S[events].pos=i;
  131.                 S[events].val=groupSize[i];
  132.                 S[events].type=0;
  133.                 events++;
  134.             }
  135.         }
  136.        
  137.         for(i=0;i<q;i++) {
  138.            
  139.             cin >> a >> b >> c;
  140.             S[events].type=1;
  141.             S[events].a=a;
  142.             S[events].b=b;
  143.             S[events].pos=i;
  144.             S[events].val=c;
  145.            
  146.             if(startOfGroup[a] == startOfGroup[b] && endOfGroup[a] == endOfGroup[b]) { //one interval
  147.                 solved[i] = true;
  148.                 result[i] += (b-a+1 >= c ? 1 : 0);
  149.             }
  150.             else
  151.                 if(endOfGroup[a]+1 == startOfGroup[b]) { //two intervals
  152.                     solved[i] = true;
  153.                     int l = a;
  154.                     int r = endOfGroup[a];
  155.                     result[i] += (r-l+1 >= c ? 1 : 0);
  156.                    
  157.                     l = startOfGroup[b];
  158.                     r = b;
  159.                     result[i] += (r-l+1 >= c ? 1 : 0);
  160.                 } else { //3+ intervals
  161.                     solved[i] = false;
  162.                     int l = a;
  163.                     int r = endOfGroup[a];
  164.                     result[i] += (r-l+1 >= c ? 1 : 0);
  165.                    
  166.                    
  167.                     l = startOfGroup[b];
  168.                     r = b;
  169.                     result[i] += (r-l+1 >= c ? 1 : 0);
  170.                    
  171.                     S[events].a = endOfGroup[a]+1;
  172.                     S[events].b = startOfGroup[b]-1;
  173.                 }
  174.            
  175.             events++;
  176.         }
  177.        
  178.         sort(S,S+events);
  179.        
  180.         for(i=0;i<events;i++) {
  181.            
  182.             if(S[i].type==0) {
  183.                 update(1,0,n-1,S[i].pos-1);
  184.             }
  185.            
  186.             else {
  187.                 if(!solved[S[i].pos]) {
  188.                     result[S[i].pos]+=query(1,0,n-1,S[i].a-1,S[i].b-1);
  189.                 }
  190.             }
  191.         }
  192.        
  193.         for(i=0;i<q;i++) {
  194.             cout << result[i]<<endl;
  195.         }
  196.     }
  197.    
  198.     return 0;
  199. }
RAW Paste Data