Submission #1254560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254560		MercubytheFirst	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	318 ms	137336 KiB

apple

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
 
#ifdef LOCAL
#include "debug.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#else
#define debug(...) 42
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

struct DSU
{
    vector<int> dsu, val;
    DSU(int sz) : dsu(sz+1, -1), val(sz+1, 0) { }
    int get(int x) {
        if(dsu[x] < 0) { 
            return x;
        }
        int par = get(dsu[x]);
        val[x] ^= val[dsu[x]];
        return dsu[x] = par;
    }
    int bit(int x) {
        get(x);
        return val[x];
    }
    bool merge(int x, int y, int b) {
        if(get(x) == get(y)) {
            return bit(x) == (bit(y) ^ b);
        }
        int px = get(x), py = get(y);
        const int eb = b ^ bit(x) ^ bit(px) ^ bit(y) ^ bit(py);
        if(dsu[px] > dsu[py]) { 
            swap(x, y);
            swap(px, py);
        }
        dsu[px] += dsu[py];
        dsu[py] = x;
        val[py] ^= eb;
    }
};

struct Node
{
    Node *lc, *rc;
    bool lazy = false;
    int sum = 0;
    Node() : lc(NULL), rc(NULL) { }
    void extend() {
        if(!lc) { 
            lc = new Node();
            lc->lazy |= lazy;
        }
        if(!rc) {
            rc = new Node();
            rc->lazy |= lazy;
        }
    }
    void push(int lb, int rb) {
        if(!lazy) { return; }
        if(lazy) { sum = rb - lb + 1; }
        if(lb == rb) { return; }
        if(lc) {
            lc->lazy |= lazy;
        }
        if(rc) {
            rc->lazy |= lazy;
        }
        return;
    }
    void add(int L, int R, int x, int lb, int rb) {
        push(lb, rb);
        if(rb < L or R < lb) { return; }
        debug(lb, rb, sum);
        if(L <= lb and rb <= R) {
            lazy = 1;
            push(lb, rb);
            return;
        }
        extend();
        const int m = (lb + rb) / 2; 
        lc->add(L, R, x, lb, m);
        rc->add(L, R, x, m+1, rb);
        sum = lc->sum + rc->sum;
    }
    int get(int L, int R, int lb, int rb) {
        push(lb, rb);
        if(rb < L or R < lb) { return 0; }
        debug(lb, rb, sum);
        if(L <= lb and rb <= R) {
            return sum;
        }
        extend();
        const int m = (lb + rb) / 2;
        return lc->get(L, R, lb, m) + rc->get(L, R, m+1, rb);
    }
};

void solve() {
    const int inf = 1e9 + 37;
    int Q, C = 0;
    cin >> Q;
    Node* root = new Node();
    while(Q--) {
        int qt, x, y;
        cin >> qt >> x >> y;
        x += C, y += C;
        if(qt == 1) {
            debug("getting");
            C = root->get(x, y, 0, inf);
            cout << C << '\n';
        }
        else if(qt == 2){
            debug("adding");
            root->add(x, y, 1, 0, inf);
        }
        else {
            assert(false);
        }
    }
}
 
signed main(){
    #ifdef LOCAL
    freopen("test.err", "w", stderr);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    signed T = 1;
    // cin >> T;
    for(signed test = 1; test <= T; ++test){
        solve();
    }
} 

• Subtask 1: 100 / 100