Submission #684049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684049	2023-01-20T07:50:57 Z	nifeshe	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	571 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;
    node() {
        lf = nullptr;
        rt = nullptr;
    }

    void push(int l, int r) {
        if(r - l > 1 && !lf) lf = new node();
        if(r - l > 1 && !rt) rt = new node();
        if(!add) return;
        s = add * (r - l);
        if(r - l > 1) {
            lf -> add = add;
            rt -> add = add;
        }
        add = 0;
    }

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

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

node SegTree;

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	15 ms	5972 KB	Output is correct
5	Correct	19 ms	7164 KB	Output is correct
6	Correct	19 ms	6868 KB	Output is correct
7	Correct	19 ms	7124 KB	Output is correct
8	Correct	157 ms	52324 KB	Output is correct
9	Correct	311 ms	89128 KB	Output is correct
10	Correct	308 ms	99748 KB	Output is correct
11	Correct	330 ms	108448 KB	Output is correct
12	Correct	318 ms	111856 KB	Output is correct
13	Correct	309 ms	138956 KB	Output is correct
14	Correct	313 ms	140364 KB	Output is correct
15	Correct	571 ms	254852 KB	Output is correct
16	Correct	518 ms	256592 KB	Output is correct
17	Correct	319 ms	145440 KB	Output is correct
18	Correct	313 ms	145380 KB	Output is correct
19	Correct	517 ms	262144 KB	Output is correct
20	Correct	536 ms	262144 KB	Output is correct