Submission #920650

#	Time	Username	Problem	Language	Result	Execution time	Memory
920650		Irate	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	291 ms	170064 KiB

apple

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
    vector<int>sTree, L, R;
    int nxt = 2;
    SegmentTree(int n){
        sTree.resize(144 * n);
        L.resize(144 * n);
        R.resize(144 * n);
    }
    void Propagate(int node, int l, int r){
        if(sTree[node] != r - l + 1)return;
        if(l != r){
            if(L[node] == 0)L[node] = nxt++;
            if(R[node] == 0)R[node] = nxt++;
            int mid = (l + r) >> 1;
            sTree[L[node]] = mid - l + 1;
            sTree[R[node]] = r - mid;
        }
    }
    void R_Update(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            sTree[node] = r - l + 1;
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr)return;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        R_Update(L[node], l, mid, ql, qr);
        R_Update(R[node], mid + 1, r, ql, qr);
        sTree[node] = sTree[L[node]] + sTree[R[node]];
    }
    int Query(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            return sTree[node];
        }
        if(ql > r || l > qr)return 0;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        int lc = Query(L[node], l, mid, ql, qr);
        int rc = Query(R[node], mid + 1, r, ql, qr);
        return lc + rc;
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q, c = 0;
    cin >> q;
    SegmentTree tree(q);
    int n = 1e9;
    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        l += c;
        r += c;
        if(type == 1){
            c = tree.Query(1, 1, n, l, r);
            cout << c << '\n';
        }
        else{
            tree.R_Update(1, 1, n, l, r);
        }
    }
}

• Subtask 1: 100 / 100