Submission #669990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669990	2022-12-07T17:17:20 Z	gortomi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	39 ms	3072 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l, r, sum;
    bool lazy;
    node* lc;
    node* rc;
    node(int il, int ir)
    {
        l = il;
        r = ir;
        lazy = 0;
        sum = 0;
        lc = nullptr;
        rc = nullptr;
    }
    void next()
    {
        if(lc != nullptr) return;
        int m = (l + r) / 2;
        lc = new node(l, m);
        rc = new node(m + 1, r);
    }
    int val(int ql, int qr)
    {
        if(ql > qr) return 0;
        if(ql == l && qr == r)
        {
            return sum;
        }
        if(lazy) return qr - ql + 1;
        next();
        int m = (l + r) / 2;
        return lc -> val(ql, min(m, qr)) + rc -> val(max(ql, m  + 1), qr);
    }
    void upd(int ul, int ur)
    {
        if(ul > ur) return;
        if(ul == l && ur == r)
        {
            lazy = 1;
            sum = r - l + 1;
            return;
        }
        if(lazy) return;
        next();
        int m = (l + r) / 2;
        lc -> upd(ul, min(m, ur));
        rc -> upd(max(ul, m  + 1), ur);
        sum = lc -> sum + rc -> sum;
    }
};
node root = node(1, 1e9);
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, type, il, ir, c = 0;
    cin >> m;
    while(m--)
    {
        cin >> type >> il >> ir;
        if(type == 1)
        {
            c = root.val(il + c, ir + c);
            cout << c << "\n";
        }
        if(type == 2) root.upd(il + c, ir + c);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	18 ms	1488 KB	Output is correct
9	Correct	35 ms	2476 KB	Output is correct
10	Correct	34 ms	2512 KB	Output is correct
11	Correct	33 ms	2508 KB	Output is correct
12	Correct	34 ms	2508 KB	Output is correct
13	Correct	38 ms	2892 KB	Output is correct
14	Correct	39 ms	2764 KB	Output is correct
15	Correct	36 ms	3020 KB	Output is correct
16	Correct	35 ms	3028 KB	Output is correct
17	Correct	29 ms	2892 KB	Output is correct
18	Correct	30 ms	2900 KB	Output is correct
19	Correct	35 ms	3024 KB	Output is correct
20	Correct	34 ms	3072 KB	Output is correct