Submission #963503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963503	2024-04-15T07:44:33 Z	Esgeer	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	153228 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 = 1e5+5;

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
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	150624 KB	Output is correct
2	Correct	35 ms	150504 KB	Output is correct
3	Correct	35 ms	150724 KB	Output is correct
4	Correct	43 ms	150776 KB	Output is correct
5	Correct	56 ms	150868 KB	Output is correct
6	Correct	53 ms	150892 KB	Output is correct
7	Correct	47 ms	150864 KB	Output is correct
8	Correct	136 ms	151660 KB	Output is correct
9	Correct	224 ms	152840 KB	Output is correct
10	Correct	224 ms	153064 KB	Output is correct
11	Correct	240 ms	152908 KB	Output is correct
12	Correct	218 ms	152804 KB	Output is correct
13	Correct	203 ms	153188 KB	Output is correct
14	Correct	204 ms	153228 KB	Output is correct
15	Execution timed out	2071 ms	153020 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-