Submission #466899

#	Time	Username	Problem	Language	Result	Execution time	Memory
466899		SirCovidThe19th	Ruka (COI15_ruka)	C++17	100 / 100	834 ms	17440 KiB

ruka

#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);
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56