Submission #684048

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684048	2023-01-20T07:47:37 Z	nifeshe	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	420 ms	262144 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
//#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e9 + 5;
const int MAX = 1e6 + 5;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

struct node {
    node *lf, *rt;
    int s = 0;
    bool add = 0;
    int tl = 0, tr = 0;
    node() {
        lf = nullptr;
        rt = nullptr;
    }

    node(int L, int R) {
        lf = nullptr;
        rt = nullptr;
        tl = L;
        tr = R;
    }

    void push() {
        int tm = (tl + tr) / 2;
        if(tr - tl > 1 && !lf) lf = new node(tl, tm);
        if(tr - tl > 1 && !rt) rt = new node(tm, tr);
        if(!add) return;
        s = add * (tr - tl);
        if(tr - tl > 1) {
            lf -> add = add;
            rt -> add = add;
        }
        add = 0;
    }

    int get(int l, int r) {
        push();
        if(r <= tl || tr <= l) return 0;
        if(l <= tl && tr <= r) return s;
        return (lf -> get(l, r)) + (rt -> get(l, r));
    }

    void update(int l, int r, int x) {
        push();
        if(r <= tl || tr <= l) return;
        if(l <= tl && tr <= r) {
            add = x;
            push();
            return;
        }
        lf -> update(l, r, x);
        rt -> update(l, r, x);
        s = lf -> s + rt -> s;
    }
};

node SegTree(0, inf);

void solve() {
    int q;
    cin >> q;
    int lst = 0;
    while(q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += lst, r += lst;
        l--;
        if(t == 1) cout << (lst = SegTree.get(l, r)) << '\n';
        else SegTree.update(l, r, 1);
    }
}

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message

apple.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	21 ms	8744 KB	Output is correct
5	Correct	21 ms	10424 KB	Output is correct
6	Correct	19 ms	10112 KB	Output is correct
7	Correct	20 ms	10496 KB	Output is correct
8	Correct	167 ms	77776 KB	Output is correct
9	Correct	364 ms	132560 KB	Output is correct
10	Correct	337 ms	148624 KB	Output is correct
11	Correct	398 ms	161248 KB	Output is correct
12	Correct	357 ms	166600 KB	Output is correct
13	Correct	352 ms	207032 KB	Output is correct
14	Correct	349 ms	209216 KB	Output is correct
15	Runtime error	420 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-