oj.uz

Submission #466899

# Submission time Handle Problem Language Result Execution time Memory
466899 2021-08-21T02:31:36 Z SirCovidThe19th Ruka (COI15_ruka) C++17
100 / 100
 834 ms 17440 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 323 ms 9708 KB Output is correct
6 Correct 295 ms 10464 KB Output is correct
7 Correct 351 ms 8432 KB Output is correct
8 Correct 351 ms 8548 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 323 ms 9708 KB Output is correct
6 Correct 295 ms 10464 KB Output is correct
7 Correct 351 ms 8432 KB Output is correct
8 Correct 351 ms 8548 KB Output is correct
9 Correct 808 ms 16084 KB Output is correct
10 Correct 834 ms 17440 KB Output is correct
11 Correct 763 ms 13616 KB Output is correct
12 Correct 731 ms 13264 KB Output is correct