Submission #963513

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963513	2024-04-15T07:56:22 Z	Esgeer	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	294 ms	186452 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) {}  
};

Node t[64*N];
int idx = 0;

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 = ++idx;
        t[idx].tl = t[node].tl;
        t[idx].tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = ++idx;
        t[idx].tl = mid+1;
        t[idx].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 = ++idx;
            t[idx].tl = t[node].tl;
            t[idx].tr = mid;
        }
        if(t[node].r == -1) {
            t[node].r = ++idx;
            t[idx].tl = mid+1;
            t[idx].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 = ++idx;
        t[idx].tl = t[node].tl;
        t[idx].tr = mid;
    }
    if(t[node].r == -1) {
        t[node].r = ++idx;
        t[idx].tl = mid+1;
        t[idx].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	87 ms	185940 KB	Output is correct
2	Correct	51 ms	185820 KB	Output is correct
3	Correct	48 ms	185940 KB	Output is correct
4	Correct	55 ms	185940 KB	Output is correct
5	Correct	58 ms	185936 KB	Output is correct
6	Correct	70 ms	185816 KB	Output is correct
7	Correct	58 ms	185940 KB	Output is correct
8	Correct	121 ms	186152 KB	Output is correct
9	Correct	210 ms	186312 KB	Output is correct
10	Correct	225 ms	186300 KB	Output is correct
11	Correct	235 ms	186164 KB	Output is correct
12	Correct	231 ms	186348 KB	Output is correct
13	Correct	194 ms	186416 KB	Output is correct
14	Correct	205 ms	186244 KB	Output is correct
15	Correct	266 ms	186348 KB	Output is correct
16	Correct	271 ms	186312 KB	Output is correct
17	Correct	192 ms	186304 KB	Output is correct
18	Correct	201 ms	186452 KB	Output is correct
19	Correct	280 ms	186400 KB	Output is correct
20	Correct	294 ms	186448 KB	Output is correct