Submission #467699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467699	2021-08-24T06:00:00 Z	jli12345	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	348 ms	103352 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	100548 KB	Output is correct
2	Correct	53 ms	100512 KB	Output is correct
3	Correct	58 ms	100504 KB	Output is correct
4	Correct	62 ms	100696 KB	Output is correct
5	Correct	65 ms	100744 KB	Output is correct
6	Correct	71 ms	100684 KB	Output is correct
7	Correct	67 ms	100668 KB	Output is correct
8	Correct	136 ms	101592 KB	Output is correct
9	Correct	252 ms	102604 KB	Output is correct
10	Correct	255 ms	102688 KB	Output is correct
11	Correct	226 ms	102724 KB	Output is correct
12	Correct	258 ms	102880 KB	Output is correct
13	Correct	248 ms	103140 KB	Output is correct
14	Correct	217 ms	103200 KB	Output is correct
15	Correct	276 ms	103156 KB	Output is correct
16	Correct	303 ms	103352 KB	Output is correct
17	Correct	225 ms	103160 KB	Output is correct
18	Correct	241 ms	103056 KB	Output is correct
19	Correct	283 ms	103304 KB	Output is correct
20	Correct	348 ms	103208 KB	Output is correct