Submission #504070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
504070	2022-01-09T15:59:16 Z	CodeChamp_SS	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	491 ms	208764 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 = 1e9 + 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();

    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 (qs > r or qe < l) return;

        if (cur->push) push(cur, l, r);

        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, N);
    }

    int query(int qs, int qe, Node *cur, int l, int r) {
        if (qs > r or qe < l) return 0;

        if (cur->push) push(cur, l, r);

        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, N);
    }
} 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

100.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	1 ms	204 KB	Output is correct
4	Correct	13 ms	4812 KB	Output is correct
5	Correct	22 ms	5908 KB	Output is correct
6	Correct	16 ms	5600 KB	Output is correct
7	Correct	17 ms	5872 KB	Output is correct
8	Correct	124 ms	44144 KB	Output is correct
9	Correct	255 ms	76700 KB	Output is correct
10	Correct	317 ms	84588 KB	Output is correct
11	Correct	271 ms	90988 KB	Output is correct
12	Correct	323 ms	93684 KB	Output is correct
13	Correct	259 ms	108488 KB	Output is correct
14	Correct	293 ms	109564 KB	Output is correct
15	Correct	415 ms	202704 KB	Output is correct
16	Correct	442 ms	204204 KB	Output is correct
17	Correct	266 ms	115340 KB	Output is correct
18	Correct	271 ms	115364 KB	Output is correct
19	Correct	491 ms	208648 KB	Output is correct
20	Correct	413 ms	208764 KB	Output is correct