Submission #643296

#	Time	Username	Problem	Language	Result	Execution time	Memory
643296		KYoA_A	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	52 ms	2976 KiB

apple

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif

#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define vi vector<int>
#define ar array

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()

#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second

#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

const int SZ = 1<<30;
template<class T> struct node {
	T val = 0; node<T>* c[2]; bool ok = 0;
	node() { c[0] = c[1] = NULL; }
	void upd(int l, int r, int L = 0, int R = SZ-1) { // add v
		if(R < l || L > r || ok) return;
		if (l <= L && R <= r) {
			ok = 1;
			val = R - L + 1; return;
		}

		int M = (L+R)/2;
		if (!c[0]) c[0] = new node();
		c[0]->upd(l,r,L,M);

		if (!c[1]) c[1] = new node();
		c[1]->upd(l,r,M+1,R);

		val = 0; rep(i, 0, 2) val += c[i]->val;
	}
	T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
		if (hi < L || R < lo) return 0;
		if (lo <= L && R <= hi) return val;
		if(ok) return min(R, hi) - max(lo, L) + 1;
		int M = (L+R)/2; T res = 0;
		if (c[0]){
			res += c[0]->query(lo,hi,L,M);
		}
		if (c[1]) {
			res += c[1]->query(lo,hi,M+1,R);
		}

		return res;
	}
	void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
		if (L != R) {
			int M = (L+R)/2;
			if (ind <= M) {
				if (!c[0]) c[0] = new node();
				c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
			} else {
				if (!c[1]) c[1] = new node();
				c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
			}
		} 
		val = (c0?c0->val:0)+(c1?c1->val:0);
	}
};


node<int> rt;

void solve(){
	int q; cin >> q;
	int c = 0;
	while(q--){
		int t, a, b; cin >> t >> a >> b;
		a += c; b += c;

		if(t&1){
			c = rt.query(a, b);
			cout << c << '\n';
		}else{
			rt.upd(a, b);
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();
}

• Subtask 1: 100 / 100