Submission #963505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963505	2024-04-15T07:46:48 Z	Esgeer	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	151168 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	66 ms	150612 KB	Output is correct
2	Correct	37 ms	150616 KB	Output is correct
3	Correct	36 ms	150552 KB	Output is correct
4	Correct	40 ms	150608 KB	Output is correct
5	Correct	47 ms	150624 KB	Output is correct
6	Correct	45 ms	150724 KB	Output is correct
7	Correct	42 ms	150712 KB	Output is correct
8	Correct	101 ms	150864 KB	Output is correct
9	Correct	193 ms	151120 KB	Output is correct
10	Correct	221 ms	151088 KB	Output is correct
11	Correct	220 ms	151124 KB	Output is correct
12	Correct	251 ms	150884 KB	Output is correct
13	Correct	185 ms	151168 KB	Output is correct
14	Correct	212 ms	151088 KB	Output is correct
15	Execution timed out	2029 ms	151120 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-