Submission #504066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
504066	2022-01-09T15:54:20 Z	CodeChamp_SS	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	465 ms	262148 KB

apple

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

using namespace __gnu_pbds;
using namespace std;

#define ff                  first
#define ss                  second
#define pb                  push_back
#define eb                  emplace_back
#define mp                  make_pair
#define lb                  lower_bound
#define ub                  upper_bound
#define setbits(x)          __builtin_popcountll(x)
#define trailing_zeros(x)   __builtin_ctzll(x)
#define leading_zeros(x)    __builtin_clzll(x)
#define sz(v)               (int)v.size()
#define ps(y)               cout << fixed << setprecision(y)
#define ms(arr, v)          memset(arr, v, sizeof(arr))
#define all(v)              v.begin(), v.end()
#define rall(v)             v.rbegin(), v.rend()
#define trav(x, v)          for(auto &x: v)
#define w(t)                int t; cin >> t; while(t--)
#define rep(i, a, b)        for(int i = a; i <= b; i++)
#define rrep(i, a, b)       for(int i = a; i >= b; i--)
#define rep0(i, n)          rep(i, 0, n - 1)
#define rrep0(i, n)         rrep(i, n - 1, 0)
#define rep1(i, n)          rep(i, 1, n)
#define rrep1(i, n)         rrep(i, n, 1)
#define inp(arr, n)         rep0(i, n) cin >> arr[i];

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef map<ll, ll> mii;
typedef map<char, ll> mci;
typedef priority_queue<ll> pq_mx;
typedef priority_queue<ll, vi, greater<>> pq_mn;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*
 * find_by_order(i) -> returns an iterator to the element at ith position (0 based)
 * order_of_key(i)  -> returns the position of element i (0 based)
 */

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll inf = 2e18;
const ld eps = 1e-10, pi = acos(-1.0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fio() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}

struct Node {
    Node *l, *r;
    ll sum;
    bool push;

    Node() : l(nullptr), r(nullptr), sum(0ll), push(false) {}
};

struct SparseSegTree {
    Node *root = new Node();
    ll dummy = 0;
    const int M = 1e9 + 5;

    void push(Node *cur, ll l, ll r) {
        if (!cur->l) cur->l = new Node();
        if (!cur->r) cur->r = new Node();
        cur->push = false;
        ll m = (l + r) / 2;
        cur->l->sum = m - l + 1, cur->l->push = true;
        cur->r->sum = r - m, cur->r->push = true;
    }

    void update(ll qs, ll qe, Node *cur, ll l, ll r) {
        if (cur->push) push(cur, l, r);

        if (qs > r or qe < l) return;

        if (l >= qs and r <= qe) {
            cur->sum = r - l + 1, cur->push = true;
            push(cur, l, r);
            return;
        }

        ll m = (l + r) / 2;
        if (!cur->l) cur->l = new Node();
        if (!cur->r) cur->r = new Node();
        update(qs, qe, cur->l, l, m), update(qs, qe, cur->r, m + 1, r);
        cur->sum = cur->l->sum + cur->r->sum;
    }

    void update(ll qs, ll qe) {
        update(qs, qe, root, 0, M);
    }

    ll query(ll qs, ll qe, Node *cur, ll l, ll r) {
        if (cur->push) push(cur, l, r);

        if (qs > r or qe < l) return dummy;

        if (l >= qs and r <= qe) return cur->sum;

        ll m = (l + r) / 2;
        if (!cur->l) cur->l = new Node();
        if (!cur->r) cur->r = new Node();
        return query(qs, qe, cur->l, l, m) + query(qs, qe, cur->r, m + 1, r);
    }

    ll query(ll qs, ll qe) {
        return query(qs, qe, root, 0, M);
    }
} st;

int main() {
    fio();

    ll c = 0;
    w(t) {
        ll o, i, j;
        cin >> o >> i >> j, i += c, j += c;
        if (o == 2) st.update(i, j);
        else c = st.query(i, j), cout << c << '\n';
    }

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	320 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	316 KB	Output is correct
4	Correct	19 ms	9564 KB	Output is correct
5	Correct	21 ms	11608 KB	Output is correct
6	Correct	26 ms	11084 KB	Output is correct
7	Correct	20 ms	11492 KB	Output is correct
8	Correct	185 ms	87616 KB	Output is correct
9	Correct	358 ms	152488 KB	Output is correct
10	Correct	377 ms	168340 KB	Output is correct
11	Correct	377 ms	180900 KB	Output is correct
12	Correct	379 ms	186576 KB	Output is correct
13	Correct	400 ms	217276 KB	Output is correct
14	Correct	406 ms	219332 KB	Output is correct
15	Runtime error	465 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-