답안 #848957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848957 2023-09-13T18:32:42 Z Ahmed_Solyman 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
234 ms 187028 KB
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("O3")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define F first
#define S second
#define MP make_pair
#define endl '\n'
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;

void push_lazy(int node) {
	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}

void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}

		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}

int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fast
    int m;
	cin >> m;

	segtree[1].tl = 1;
	segtree[1].tr = 1e9;

	int c = 0;
    while(m--){
        int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = query(1, x + c, y + c);
			cout << c << '\n';
		} else update(1, x + c, y + c);
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 185952 KB Output is correct
2 Correct 29 ms 185948 KB Output is correct
3 Correct 30 ms 185804 KB Output is correct
4 Correct 38 ms 185948 KB Output is correct
5 Correct 39 ms 185996 KB Output is correct
6 Correct 39 ms 186008 KB Output is correct
7 Correct 40 ms 185936 KB Output is correct
8 Correct 98 ms 186252 KB Output is correct
9 Correct 185 ms 186232 KB Output is correct
10 Correct 197 ms 186392 KB Output is correct
11 Correct 187 ms 186196 KB Output is correct
12 Correct 192 ms 186180 KB Output is correct
13 Correct 171 ms 186248 KB Output is correct
14 Correct 167 ms 186448 KB Output is correct
15 Correct 234 ms 186496 KB Output is correct
16 Correct 230 ms 186364 KB Output is correct
17 Correct 181 ms 187028 KB Output is correct
18 Correct 178 ms 186452 KB Output is correct
19 Correct 229 ms 186440 KB Output is correct
20 Correct 233 ms 186508 KB Output is correct