Submission #963514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963514	2024-04-15T08:00:39 Z	Esgeer	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	335 ms	199620 KB

apple

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
//#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp << " " <<
#define F(i, s, n) for(int i = s; i < n; i++)
#define pb push_back
#define fi first
#define se second

int mod = 1e9+7;
int inf = 1e6;
const int N = 123456;

struct Node {
    int sum, lazy, l, r, tl, tr;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}  
};

vector<Node> t(1);

void push(int node) {
    if(t[node].lazy == 0) return;
    t[node].sum = t[node].tr - t[node].tl + 1;

    int mid = (t[node].tl + t[node].tr) >> 1;

    if(t[node].l == -1) {
        t[node].l = t.size();
        t.pb({});
        t.back().tl = t[node].tl;
        t.back().tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = t.size();
        t.pb({});
        t.back().tl = mid+1;
        t.back().tr = t[node].tr;
    }

    t[t[node].l].lazy = 1;
    t[t[node].r].lazy = 1;
    t[node].lazy = 0;
}

void update(int node, int l, int r) {
    push(node);
    if(t[node].tl == l && t[node].tr == r) {
        t[node].lazy = 1;
        push(node);
    } else {
        int mid = (t[node].tl + t[node].tr) >> 1;

        if(t[node].l == -1) {
            t[node].l = t.size();
            t.pb({});
            t.back().tl = t[node].tl;
            t.back().tr = mid;
        }
        if(t[node].r == -1) {
            t[node].r = t.size();
            t.pb({});
            t.back().tl = mid+1;
            t.back().tr = t[node].tr;
        }

        if(l > mid) update(t[node].r, l, r);
        else if(r <= mid) update(t[node].l, l, r);
        else {
            update(t[node].l, l, mid);
            update(t[node].r, mid+1, r);
        }
        // REMOVED UNNECESSARY PUSH OPERATIONS - seems like they re necessary :/
        push(t[node].l);
        push(t[node].r);
        t[node].sum = t[t[node].l].sum + t[t[node].r].sum;
    }
}

int query(int node, int l, int r) {
    push(node);
    if(t[node].tl == l && t[node].tr == r) return t[node].sum;
    int mid = (t[node].tl + t[node].tr) >> 1;

    if(t[node].l == -1) {
        t[node].l = t.size();
        t.pb({});
        t.back().tl = t[node].tl;
        t.back().tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = t.size();
        t.pb({});
        t.back().tl = mid+1;
        t.back().tr = t[node].tr;
    }

    if(l > mid) return query(t[node].r, l, r);
    else if(r <= mid) return query(t[node].l, l, r);
    else return query(t[node].l, l, mid) + query(t[node].r, mid+1, r);
}

void solve() {
    int n;
    cin >> n;
    t[0].tl = 0;
    t[0].tr = 1e9;
    t[0].sum = 0;
    t[0].lazy = 0;
    t[0].l = -1;
    t[0].r = -1;

    int c = 0;

    F(i, 0, n) {
        int type, a, b;
        cin >> type >> a >> b;
        if(type == 1) {
            c = query(0, a + c, b + c);
            cout << c << endl;
        } else update(0, a + c, b + c);
    }
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Local
        freopen("local.in", "r", stdin);
        freopen("local.out", "w", stdout);
    #else 
        // freopen("poetry.in","r",stdin);
        // freopen("poetry.out","w",stdout);
    #endif
}

signed main() {
    setIO();
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	12 ms	6848 KB	Output is correct
5	Correct	15 ms	7112 KB	Output is correct
6	Correct	13 ms	8904 KB	Output is correct
7	Correct	14 ms	8392 KB	Output is correct
8	Correct	107 ms	51092 KB	Output is correct
9	Correct	223 ms	99316 KB	Output is correct
10	Correct	218 ms	100292 KB	Output is correct
11	Correct	225 ms	101132 KB	Output is correct
12	Correct	223 ms	100760 KB	Output is correct
13	Correct	199 ms	100764 KB	Output is correct
14	Correct	206 ms	99232 KB	Output is correct
15	Correct	335 ms	198028 KB	Output is correct
16	Correct	329 ms	199044 KB	Output is correct
17	Correct	201 ms	99888 KB	Output is correct
18	Correct	217 ms	101436 KB	Output is correct
19	Correct	316 ms	199620 KB	Output is correct
20	Correct	332 ms	198516 KB	Output is correct