Submission #467699

#	Time	Username	Problem	Language	Result	Execution time	Memory
467699		jli12345	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	348 ms	103352 KiB

apple

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

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

struct Node{
    int lson, rson;
    int sum;
    int settag;
    Node(){
        lson = rson = -1;
        sum = 1;
        settag = -1;
    }
} st[64*100100];

int nodecnt = 1;

void pushdown(int node, int l, int mid, int r){
    if (st[node].lson == -1)
        st[node].lson = ++nodecnt;
    if (st[node].rson == -1)
        st[node].rson = ++nodecnt;
    if (st[node].settag == -1)
        return;
    st[st[node].lson].sum = (mid-l+1)*st[node].settag;
    st[st[node].rson].sum = (r-mid)*st[node].settag;
    st[st[node].lson].settag = st[st[node].rson].settag = st[node].settag;
    st[node].settag = -1;
}

void U(int node, int l, int r, int tl, int tr, int val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node].sum = (r-l+1)*val;
        st[node].settag = val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(st[node].lson, l, mid, tl, tr, val);
    U(st[node].rson, mid+1, r, tl, tr, val);
    st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}

int S(int node, int l, int r, int tl, int tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr){
        return st[node].sum;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return S(st[node].lson, l, mid, tl, tr)+S(st[node].rson, mid+1, r, tl, tr);
}

int main(){
    fastIO();
    int Q; cin >> Q;
    int C = 0;
    U(1, 1, 1000000000, 1, 1000000000, 0);
    while (Q--){
        int k; cin >> k;
        int a, b; cin >> a >> b;
        if (k == 1){
            int val = S(1, 1, 1000000000, a+C, b+C);
            cout << val << "\n";
            C = val;
        } else {
            U(1, 1, 1000000000, a+C, b+C, 1);
        }
    }
}

• Subtask 1: 100 / 100