oj.uz

답안 #643296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643296 2022-09-21T17:14:53 Z KYoA_A 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 52 ms 2976 KB 
/*---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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 452 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 23 ms 1468 KB Output is correct
9 Correct 39 ms 2436 KB Output is correct
10 Correct 39 ms 2424 KB Output is correct
11 Correct 36 ms 2424 KB Output is correct
12 Correct 36 ms 2480 KB Output is correct
13 Correct 47 ms 2764 KB Output is correct
14 Correct 49 ms 2876 KB Output is correct
15 Correct 36 ms 2976 KB Output is correct
16 Correct 36 ms 2928 KB Output is correct
17 Correct 47 ms 2792 KB Output is correct
18 Correct 52 ms 2764 KB Output is correct
19 Correct 35 ms 2940 KB Output is correct
20 Correct 35 ms 2948 KB Output is correct