Guest User

Untitled

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