SHARE
TWEET

Untitled

a guest Nov 21st, 2019 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define asp ""
  4. #define aps ''
  5. #define one 1
  6. #define two 2
  7. #define dif !=
  8. const int maxn = 1e5 + 5;
  9. struct Node{
  10.     int menor,igual,maior;
  11. };
  12. vector<Node> tree(4*maxn);
  13.  
  14. void update(int pos,int i,int j,int x,int val){
  15.  
  16.     int esq = two*pos;
  17.     int dir = two*pos + one;
  18.     int mid = (i+j)/two;
  19.  
  20.     if(i == j){
  21.         if(val == 0){
  22.             tree[pos].igual = one;
  23.             tree[pos].menor = 0;
  24.             tree[pos].maior = 0;
  25.         }
  26.         else if(val == one){
  27.             tree[pos].igual = 0;
  28.             tree[pos].menor = 0;
  29.             tree[pos].maior = one;
  30.         }
  31.         else{
  32.             tree[pos].igual = 0;
  33.             tree[pos].menor = one;
  34.             tree[pos].maior = 0;
  35.         }
  36.     }
  37.     else{
  38.  
  39.         if(x <= mid) update(esq,i,mid,x,val);
  40.         else update(dir,mid+one,j,x,val);
  41.  
  42.         tree[pos].igual = tree[esq].igual + tree[dir].igual;
  43.         tree[pos].maior = tree[esq].maior + tree[dir].maior;
  44.         tree[pos].menor = tree[esq].menor + tree[dir].menor;
  45.     }
  46. }
  47.  
  48. Node query(int pos,int i,int j,int l,int r){
  49.  
  50.     int esq = two*pos;
  51.     int dir = two*pos + one;
  52.     int mid = (i+j)/two;
  53.     Node aux = {0,0,0};
  54.     Node auxa = {0,0,0};
  55.  
  56.     if(i > r || j < l) return aux;
  57.     else if(i >= l && j <= r) return tree[pos];
  58.     else{
  59.         aux = query(esq,i,mid,l,r);
  60.         auxa = query(dir,mid+one,j,l,r);
  61.         aux.igual += auxa.igual;
  62.         aux.menor += auxa.menor;
  63.         aux.maior += auxa.maior;
  64.     }
  65.  
  66.     return aux;
  67. }
  68.  
  69. int main(){
  70.  
  71.     int n,k;
  72.     while(scanf("%d %d",&n,&k) == two){
  73.         vector<char> kkk;
  74.         for(int i=0;i<n;i++){
  75.             int a;
  76.             scanf("%d",&a);
  77.             if(a < 0) a = -one;
  78.             if(a > 0) a = one;
  79.             update(one,0,n-one,i,a);
  80.         }
  81.  
  82.         while(k--){
  83.             int l, r;
  84.             char op;
  85.             scanf(" %c %d %d",&op,&l,&r);
  86.             if(op == 'C'){
  87.                 l--;
  88.                 if(r > 0) r = one;
  89.                 if(r < 0) r = -one;
  90.                 update(one,0,n-one,l,r);
  91.                 continue;
  92.             }
  93.             l--;
  94.             r--;
  95.             Node ans = query(one,0,n-one,l,r);
  96.             if(ans.igual > 0) kkk.push_back('0');
  97.             else if(ans.menor%two == 0) kkk.push_back('+');
  98.             else kkk.push_back('-');
  99.         }
  100.         for(int i=0;i<kkk.size();i++){
  101.             printf("%c",kkk[i]);
  102.         }
  103.         printf("\n");
  104.     }
  105. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top