Submission #1172899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172899		zyadhany	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	226 ms	132344 KiB

apple

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<ll>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}

using namespace std;

const int MODE = 998244353;

class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
		int lazy = 0;
		int left = -1;
		int right = -1;
	};
	vector<Node> tree;
	const int n;
	int timer = 0;

	int comb(int a, int b) { return a + b; }

	void apply(int cur, int len, int val) {
		if (val == 1) {
			tree[cur].lazy = val;
			tree[cur].freq = len * val;
		}
	}

	void push_down(int cur, int l, int r) {
		if (tree[cur].left == -1) {
			tree[cur].left = ++timer;
			tree.push_back(Node());
		}
		if (tree[cur].right == -1) {
			tree[cur].right = ++timer;
			tree.push_back(Node());
		}
		int m = (l + r) / 2;
		apply(tree[cur].left, m - l + 1, tree[cur].lazy);
		apply(tree[cur].right, r - m, tree[cur].lazy);
		tree[cur].lazy = 0;
	}

	void range_set(int cur, int l, int r, int ql, int qr, int val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			range_set(tree[cur].left, l, m, ql, qr, val);
			range_set(tree[cur].right, m + 1, r, ql, qr, val);
			tree[cur].freq =
			    comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
		}
	}

	int range_sum(int cur, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return 0; }
		if (ql <= l && r <= qr) { return tree[cur].freq; }
		push_down(cur, l, r);
		int m = (l + r) / 2;
		return comb(range_sum(tree[cur].left, l, m, ql, qr),
		            range_sum(tree[cur].right, m + 1, r, ql, qr));
	}

  public:
	SparseSegtree(int n, int q = 0) : n(n) {
		if (q > 0) { tree.reserve(2 * q * (int)log2(n)); }
		tree.push_back(Node());
	}

	void range_set(int ql, int qr, int val) { range_set(0, 0, n - 1, ql, qr, val); }

	int range_sum(int ql, int qr) { return range_sum(0, 0, n - 1, ql, qr); }
};

void solve(int tc) {
    ll n;

    cin >> n;

    SparseSegtree seg(1e9+10);

    ll c = 0;
    while (n--)
    {
        ll ty, l, r; cin >> ty >> l >> r;
        if (ty == 1) {
            c = seg.range_sum(l + c, r + c);
            cout << c << '\n';
        } else seg.range_set(l+c, r+c, 1);
    }
    
}
 
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;

    // freopen("boards.in", "r", stdin);
    // freopen("boards.out", "w", stdout);

    // cin >> size;
    for (int i = 1; i <= size; i++)
        solve(i);
}

• Subtask 1: 100 / 100