Advertisement
Guest User

INTPROD

a guest
Oct 23rd, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cctype>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. using namespace std;
  7. const int imax = 1<<18;
  8. const int level = 1<<17;
  9. int tres[imax];
  10.  
  11. void updateAll() {
  12.     for (int i = level-1; i > 0; i--) {
  13.         tres[i] = tres[2*i]*tres[2*i+1];
  14.     }
  15. }
  16.  
  17. void mod (int pos, int val) {
  18.     val = (val > 0)?1:(val<0)?-1:0;
  19.     //cout << "modded " << pos<<" "<<val<<endl;
  20.     tres[level+pos] = val;
  21.     int tcal = (level + pos)/2;
  22.     while (tcal > 0) {
  23.         tres[tcal] = tres[tcal*2] * tres[tcal*2+1];
  24.         tcal/=2;
  25.     }
  26. }
  27.  
  28. int get(int beg, int end) {
  29.     if (beg == end)
  30.         return tres[level+beg];
  31.     beg += level;
  32.     end += level;
  33.     int lval = tres[beg];
  34.     int rval = tres[end];
  35.     //cout << "l: " << beg << " " << lval << "  r:" << end << " " << rval << endl;
  36.     while (beg/2 != end/2) {
  37.         if (beg%2 == 0) {
  38.             lval *= tres[beg+1];
  39.         }
  40.         if (end%2 == 1) {
  41.             rval *= tres[end-1];
  42.         }
  43.         beg/=2;
  44.         end/=2;
  45.     }
  46.     return lval*rval;
  47. }
  48.  
  49. int main()
  50. {
  51.     //cout << (1<<17) << " " << (1<<18) << endl;
  52.     while (cin.peek() != EOF) {
  53.         int n, k;
  54.         cin >> n >> k;
  55.         for (int i = 0; i < imax; i++) {
  56.             tres[i] = 0;
  57.         }
  58.         for (int i = 0; i < n; i++) {
  59.             int tmp;
  60.             cin >> tmp;
  61.             tres[level+i] = (tmp<0)?-1:(tmp>0)?1:0;
  62.         }
  63.         updateAll();
  64.         string con;
  65.         for (int i = 0; i < k; i++) {
  66.             char c;
  67.             int a, b;
  68.             cin >> c >> a >> b;
  69.             if (c == 'C') {
  70.                 mod(a-1, b);
  71.             }
  72.             else {
  73.                 int tst = get(a-1,b-1);
  74.                 con += (tst<0)?'-':(tst>0)?'+':'0';
  75.             }
  76.         }
  77.         cout << con << endl;
  78.         cin >> ws; // purge ws
  79.     }
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement