Submission #504068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
504068	2022-01-09T15:55:46 Z	CodeChamp_SS	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	528 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 + 5;

    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	1 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	15 ms	6468 KB	Output is correct
5	Correct	20 ms	7876 KB	Output is correct
6	Correct	19 ms	7608 KB	Output is correct
7	Correct	18 ms	7752 KB	Output is correct
8	Correct	147 ms	58452 KB	Output is correct
9	Correct	308 ms	101188 KB	Output is correct
10	Correct	325 ms	111744 KB	Output is correct
11	Correct	353 ms	120272 KB	Output is correct
12	Correct	346 ms	123844 KB	Output is correct
13	Correct	311 ms	144004 KB	Output is correct
14	Correct	361 ms	145468 KB	Output is correct
15	Runtime error	528 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-