Submission #466899

#TimeUsernameProblemLanguageResultExecution timeMemory
466899SirCovidThe19thRuka (COI15_ruka)C++17
100 / 100
834 ms17440 KiB
#include <bits/stdc++.h>
using namespace std; 

#define pii pair<int, int>
#define f first
#define s second

const int mx = 3e5 + 5, off = 1.5e7 + 5;

template<int sz> struct ds{
    unordered_map<int, int> bit; int shift = 0, pt = 0, fixed = 0; pii A[sz];

    void rad(int l, int r, int x){ 
        if (l > r) swap(l, r);
        for (l += off; l <= 2 * off; l += l & (-l)) bit[l] += x; 
        for (r += off + 1; r <= 2 * off; r += r & (-r)) bit[r] -= x;
    }
    bool ok(int i){
        return min(A[i].f, A[i].s) <= 0 and max(A[i].f, A[i].s) >= 0;
    }
    void ins(int i, pii x){
        A[i] = x; rad(x.f, x.s, 1);
    }
    void upd(int x){
        x = (A[pt].f + x) - A[pt].s; 
        shift += x; 
        rad(A[pt].f, A[pt].s, -1); 
        ins(pt, {A[pt].f - x, A[pt].s});
    }
    void rht(){
        rad(A[pt].f, A[pt].s, -1);
        A[pt].f += shift, A[pt].s += shift;
        fixed += ok(pt);
        pt++;
    }
    void lft(){
        pt--;
        fixed -= ok(pt);
        A[pt].f -= shift, A[pt].s -= shift;
        rad(A[pt].f, A[pt].s, 1);
    }
    int get(){ 
        int ret = 0; 
        for (int i = -shift + off; i > 0; i -= i & (-i)) ret += bit[i];  
        return fixed + ret; 
    }
};

int n, q; ds<mx> X, Y; pii cur = {1, 1};

int main(){
	cin >> n;
    for (int i = 0; i < n; i++){
        int x, y; cin >> x >> y;  
        X.ins(i, {cur.f, cur.f + x}); Y.ins(i, {cur.s, cur.s + y});
        cur.f += x; cur.s += y;
    }
    cin >> q;
    while (q--){
        char c; cin >> c; 
        if (c == 'Q') cout<<X.get() + Y.get()<<endl;
        if (c == 'B' and X.pt > 0) X.lft(), Y.lft();
        if (c == 'F' and X.pt < n - 1) X.rht(), Y.rht();
        if (c == 'C'){
            int x, y; cin >> x >> y;
            X.upd(x); Y.upd(y);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...