제출 #1254541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254541		MercubytheFirst	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	328 ms	273260 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<ll> dsu, val;
    DSU(ll sz) : dsu(sz+1, -1), val(sz+1, 0) { }
    ll get(ll x) {
        if(dsu[x] < 0) { 
            return x;
        }
        ll par = get(dsu[x]);
        val[x] ^= val[dsu[x]];
        return dsu[x] = par;
    }
    ll bit(ll x) {
        get(x);
        return val[x];
    }
    bool merge(ll x, ll y, ll b) {
        if(get(x) == get(y)) {
            return bit(x) == (bit(y) ^ b);
        }
        ll px = get(x), py = get(y);
        const ll 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;
    ll lb, rb, sum, lazy;
    Node(ll L, ll R) : lc(NULL), rc(NULL), lb(L), rb(R), sum(0), lazy(0) { }
    void push() {
        if(lazy) { sum = rb - lb + 1; }
        if(lb == rb) { return; }
        const ll m = (lb + rb) / 2;
        if(!lc) {
            lc = new Node(lb, m);
        }
        if(!rc) {
            rc = new Node(m+1, rb);
        }
        lc->lazy |= lazy;
        rc->lazy |= lazy;
        return;
    }
    void add(ll L, ll R, ll x) {
        push();
        if(rb < L or R < lb) { return; }
        if(L <= lb and rb <= R) {
            lazy = 1;
            push();
            return;
        }
        lc->add(L, R, x);
        rc->add(L, R, x);
        sum = lc->sum + rc->sum;
    }
    ll get(ll L, ll R) {
        push();
        if(rb < L or R < lb) { return 0; }
        if(L <= lb and rb <= R) {
            return sum;
        }
        return lc->get(L, R) + rc->get(L, R);
    }
};

void solve() {
    const ll inf = 1e9 + 37;
    ll Q, C = 0;
    cin >> Q;
    Node* root = new Node(0, inf);
    while(Q--) {
        ll qt, x, y;
        cin >> qt >> x >> y;
        x += C, y += C;
        if(qt == 1) {
            debug("getting");
            C = root->get(x, y);
            cout << C << '\n';
        }
        else if(qt == 2){
            debug("adding");
            root->add(x, y, 1);
        }
        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: 0 / 100