Submission #874367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
874367	2023-11-16T18:47:46 Z	andrei_marciuc	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	314 ms	123184 KB

apple

#include <iostream>
 
using namespace std;
 
const int NMAX = 1e9;
 
struct node {
    node *lft, *rgt;
    bool lazy;
    bool todost;
    bool tododr;
    int ans;
 
    node() {
        lft = rgt = NULL;
        lazy = 0;
        ans = 0;
        todost = 0;
        tododr = 0;
    }
};
 
void create(node *nod, bool ok) {
    if(ok == 0) {
        if(nod->lft == NULL)
            nod->lft = new node();
        if(nod->todost)
            nod->lft->lazy = true;
        nod->todost = 0;
    } else {
        if(nod->rgt == NULL)
            nod->rgt = new node();
        if(nod->tododr)
            nod->rgt->lazy = true;
        nod->tododr = 0;
    }
}
 
void propag(node *nod, int st, int dr ){
    if(nod->lazy == true) {
        nod->ans = dr - st + 1;
        nod->todost = 1;
        nod->tododr = 1;
    }
    nod->lazy = 0;
}
 
void update(node *nod, int st, int dr, int a, int b) {
    propag(nod, st, dr);
    if(a <= st and dr <= b) {
        nod->lazy = 1;
        propag(nod, st, dr);
        return ;
    }

    int med = ((st + dr) >> 1);
    if(a <= med) {
        create(nod, 0);
        update(nod->lft, st, med, a, b);
    }

    if(b > med) {
        create(nod, 1);
        update(nod->rgt, med + 1, dr, a, b);
    }

    nod->ans = 0;
    if(nod->todost) {
        create(nod, 0);
        propag(nod->lft, st, med);
    }

    if(nod->lft != NULL)
        nod->ans += nod->lft->ans;
    if(nod->tododr) {
        create(nod, 1);
        propag(nod->rgt, med + 1, dr);
    }

    if(nod->rgt != NULL)
        nod->ans += nod->rgt->ans;
}
 
int query(node *nod, int st, int dr, int a, int b) {
    propag(nod, st, dr);
    if(a <= st and dr <= b) {
        return nod->ans;
    }

    int med = ((st + dr) >> 1);
    int ans = 0;

    if(a <= med) {
        create(nod, 0);
        if(nod->lft != NULL) {
            ans += query(nod->lft, st, med, a, b);
        }
    }

    if(b > med) {
        create(nod, 1);
        if(nod->rgt != NULL) {
            ans += query(nod->rgt, med + 1, dr, a, b);
        }
    }
    return ans;
}
 
 
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    node *nod = new node();
    
    while(n--) {
        int op, a, b;
        cin >> op >> a >> b;
        a += ans;
        b += ans;
        if(op == 1) {
            int val = query(nod, 1, NMAX, a, b);
            cout << val << "\n";
            ans = val;
        } else update(nod, 1, NMAX, a, b);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	3064 KB	Output is correct
5	Correct	12 ms	3676 KB	Output is correct
6	Correct	12 ms	3676 KB	Output is correct
7	Correct	12 ms	3864 KB	Output is correct
8	Correct	94 ms	26908 KB	Output is correct
9	Correct	182 ms	46676 KB	Output is correct
10	Correct	188 ms	51328 KB	Output is correct
11	Correct	220 ms	55096 KB	Output is correct
12	Correct	192 ms	56656 KB	Output is correct
13	Correct	199 ms	65600 KB	Output is correct
14	Correct	195 ms	66180 KB	Output is correct
15	Correct	314 ms	119412 KB	Output is correct
16	Correct	294 ms	120176 KB	Output is correct
17	Correct	196 ms	68604 KB	Output is correct
18	Correct	194 ms	68468 KB	Output is correct
19	Correct	302 ms	123184 KB	Output is correct
20	Correct	289 ms	122824 KB	Output is correct