Submission #504069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
504069	2022-01-09T15:57:08 Z	CodeChamp_SS	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	505 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;
    int sum;
    bool push;

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

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

    void push(Node *cur, int l, int r) {
        if (!cur->l) cur->l = new Node();
        if (!cur->r) cur->r = new Node();
        cur->push = false;
        int 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(int qs, int qe, Node *cur, int l, int 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;
        }

        int 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(int qs, int qe) {
        update(qs, qe, root, 0, M);
    }

    int query(int qs, int qe, Node *cur, int l, int 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;

        int 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);
    }

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

int main() {
    fio();

    int c = 0;
    w(t) {
        int 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	14 ms	6360 KB	Output is correct
5	Correct	20 ms	7756 KB	Output is correct
6	Correct	19 ms	7348 KB	Output is correct
7	Correct	18 ms	7628 KB	Output is correct
8	Correct	144 ms	58020 KB	Output is correct
9	Correct	294 ms	100600 KB	Output is correct
10	Correct	310 ms	111220 KB	Output is correct
11	Correct	318 ms	119668 KB	Output is correct
12	Correct	332 ms	123388 KB	Output is correct
13	Correct	301 ms	143872 KB	Output is correct
14	Correct	293 ms	145108 KB	Output is correct
15	Runtime error	505 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-