Submission #1300333

#TimeUsernameProblemLanguageResultExecution timeMemory
1300333ThunnusMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
323 ms263692 KiB
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MAXN = 1e9 + 1;

struct SegTree{
    struct Node{
        int sum, lazy, lc, rc;
        Node(int sum, int lazy, int lc, int rc) : sum(sum), lazy(lazy), lc(lc), rc(rc) {}
        Node() : Node(0, 0, -1, -1) {}
    };
    int idx = 2;
    vector<Node> st;
    SegTree() : st(2, Node()) {}

    inline int extend(){
        while(idx >= sz(st)){
            st.emplace_back(Node());
        }
        return idx++;
    }

    inline void extend(int &c){
        if(c == -1){
            c = extend();
        }
        return;
    }

    inline void combine(int v){
		int res = 0;
		if(st[v].lc != -1){
			res += st[st[v].lc].sum;
		}
		if(st[v].rc != -1){
			res += st[st[v].rc].sum;
		}
        st[v].sum = res;
        return;
    }

    inline void apply(int v, int val, int len){
        st[v].sum = len * val;
        st[v].lazy = val;
        return;
    }

    inline void propagate(int v, int tl, int mid, int tr){
        if(st[v].lazy){
            if(st[v].lc == -1){
                st[v].lc = extend();
            }
            if(st[v].rc == -1){
                st[v].rc = extend();
            }
            apply(st[v].lc, st[v].lazy, mid - tl + 1);
            apply(st[v].rc, st[v].lazy, tr - (mid + 1) + 1);
            st[v].lazy = 0;
        }
        return;
    }

    inline void update(int ul, int ur, int val, int v, int tl, int tr){
		if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            apply(v, val, tr - tl + 1);
            return;
        }
        int mid = (tl + tr) >> 1;
        propagate(v, tl, mid, tr);
        if(ul <= mid){
            if(st[v].lc == -1){
                st[v].lc = extend();
            }
            update(ul, ur, val, st[v].lc, tl, mid);
        }
        if(mid + 1 <= ur){
            if(st[v].rc == -1){
                st[v].rc = extend();
            }
            update(ul, ur, val, st[v].rc, mid + 1, tr);
        }
        combine(v);
        return;
    }

    inline int query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return 0ll;
        if(ql <= tl && tr <= qr) return st[v].sum;
        int mid = (tl + tr) >> 1;
        propagate(v, tl, mid, tr);
        if(ql <= mid && mid + 1 <= qr){
            if(st[v].lc == -1){
                st[v].lc = extend();
            }
            if(st[v].rc == -1){
                st[v].rc = extend();
            }
            return query(ql, qr, st[v].lc, tl, mid) + query(ql, qr, st[v].rc, mid + 1, tr);
        }
        else if(ql <= mid){
            if(st[v].lc == -1){
                st[v].lc = extend();
            }
            return query(ql, qr, st[v].lc, tl, mid);
        }
        else{
            if(st[v].rc == -1){
                st[v].rc = extend();
            }
            return query(ql, qr, st[v].rc, mid + 1, tr);
        }
    }
};

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
    int m, c = 0;
    cin >> m;
    SegTree st;
    while(m--){
        int d, l, r;
        cin >> d >> l >> r;
        if(d == 1){
            l += c, r += c;
            c = st.query(l, r, 1, 1, MAXN);
            cout << c << "\n";
        }
        else{
            l += c, r += c;
            st.update(l, r, 1, 1, 1, MAXN);
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...