Jaggu Playing with Balloons

  • + 0 comments

    C++ Solution

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define rep(i, a, b) for(int i = a; i < b; i++)
    #define S(x) scanf("%d", &x)
    #define P(x) printf("%d\n", x)
    
    typedef long long int LL;
    
    int X[7] = {48576, 48640, 49152, 65536, 131072, 262144, 524288};
    const int MAXN = 1000001;
    LL BIT[MAXN];
    LL val;
    
    void update(int idx, int val){
        for(int i = idx; i < MAXN; i += i &-i) BIT[i] += val;
    }
    
    LL query(int idx){
        LL res = 0;
        for(int i = idx; i; i -= i & -i) res += BIT[i];
        return res;
    }
    
    void UUU(int pos, int M, int plus){
        rep(i, 0, 50) {
            int x = pos;
            int cnt = 999;
            while(x < MAXN){
                update(x, M);
                x += x & -x;
                if(x > MAXN && x != 1048576) {
                    x -= MAXN - 1;
                    cnt--;
                }
            }
            val += cnt * M;
            pos += plus;
            if(pos > 1000000) pos -= 1000000;
        }
    }
    
    int main(){
        int Q; S(Q);
        while(Q--){
            string s; cin >> s;
            if(s == "U"){
                int pos, M, plus;
                scanf("%d%d%d", &pos, &M, &plus);
                UUU(pos, M, plus);
            } else{
                int pos1, pos2;
                if(val) rep(i,0,7) update(X[i], val);
                scanf("%d%d", &pos1, &pos2);
                printf("%lld\n", query(pos2) - query(pos1 - 1));
                val = 0;
            }
        }
        return 0;
    }