Submission #894547

#	Time	Username	Problem	Language	Result	Execution time	Memory
894547		Andrey	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	91 ms	34280 KiB

apple

#include <bits/stdc++.h>
using namespace std;

int p = 1;
vector<pair<int,int>> seg(1,{-1,-1});
vector<int> br(1);

void upd(int l, int r, int ql, int qr, int x) {
    if(l == ql && r == qr) {
        br[x] = r-l+1;
        return;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        if(seg[x].first == -1) {
            seg[x] = {p,seg[x].second};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(l,m,ql,qr,seg[x].first);
    }
    else if(ql > m) {
        if(seg[x].second == -1) {
            seg[x] = {seg[x].first,p};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(m+1,r,ql,qr,seg[x].second);
    }
    else {
        if(seg[x].first == -1) {
            seg[x] = {p,seg[x].second};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        if(seg[x].second == -1) {
            seg[x] = {seg[x].first,p};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(l,m,ql,m,seg[x].first);
        upd(m+1,r,m+1,qr,seg[x].second);
    }
    if(br[x] != r-l+1) {
        br[x] = 0;
        if(seg[x].first != -1) {
            br[x]+=br[seg[x].first];
        }
        if(seg[x].second != -1) {
            br[x]+=br[seg[x].second];
        }
    }
}

int calc(int l, int r, int ql, int qr, int x) {
    if(ql == l && qr == r) {
        return br[x];
    }
    if(br[x] == r-l+1) {
        return qr-ql+1;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        if(seg[x].first != -1) {
            return calc(l,m,ql,qr,seg[x].first);
        }
    }
    else if(ql > m) {
        if(seg[x].second != -1) {
            return calc(m+1,r,ql,qr,seg[x].second);
        }
    }
    else {
        int ans = 0;
        if(seg[x].first != -1) {
            ans+=calc(l,m,ql,m,seg[x].first);
        }
        if(seg[x].second != -1) {
            ans+=calc(m+1,r,m+1,qr,seg[x].second);
        }
        return ans;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q,l,r,p,c = 0;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> p >> l >> r;
        l+=c;
        r+=c;
        if(p == 1) {
            c = calc(1,1e9,l,r,0);
            cout << c << "\n";
        }
        else {
            upd(1,1e9,l,r,0);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100