답안 #915805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915805	2024-01-24T17:55:27 Z	Nonoze	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	336 ms	153184 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
//#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
 
using namespace std;
using namespace __gnu_pbds;
 
typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
 
struct node
{
	int left, right;
	int sum, lazy;
	int l, r;
	node() {
		sum=0, lazy=-1, left=-1, right=-1;
	}
};
 
vector<node> st(100000*32);
int cnt=1;
 
void propagate(int root, int l, int r) {
	if (st[root].lazy!=-1) {
		st[root].sum=(r-l+1)*st[root].lazy;
		if (l!=r)
		{
			int mid=(l+r)/2;
			if (st[root].left==-1) {
				st[root].left = cnt++;
				st[ st[root].left ].l=l, st[ st[root].left ].r=mid;
			}
			if (st[root].right==-1) {
				st[root].right = cnt++;
				st[ st[root].right ].l=mid+1, st[ st[root].right ].r=r;
			}
			st[ st[root].left ].lazy=st[root].lazy;
			st[ st[root].right ].lazy=st[root].lazy;
		}
		st[root].lazy=-1;
	}
}
 
int query(int root, int left, int right, int qLeft, int qRight)
{
	propagate(root, left, right);
	if (left>qRight || right<qLeft) return 0;
	if (left>=qLeft && right<=qRight) return st[root].sum;
	int mid=(left+right)/2;
	int s1=0, s2=0;
	if (st[root].left!=-1) s1=query(st[root].left, left, mid, qLeft, qRight);
	if (st[root].right!=-1) s2=query(st[root].right, mid+1, right, qLeft, qRight);
	return s1+s2;
}
 
void update(int root, int left, int right, int qLeft, int qRight, int nValue)
{
	propagate(root, left, right);
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight) {
		st[root].lazy=nValue;
		propagate(root, left, right);
		return;
	}
	int mid=(left+right)/2;
	if (st[root].left==-1) {
		st[root].left = cnt++;
		st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
	}
	if (st[root].right==-1) {
		st[root].right = cnt++;
		st[ st[root].right ].l=mid+1, st[ st[root].right ].r=right;
	}
	propagate(st[root].left, left, mid), propagate(st[root].right, mid+1, right);
	if (mid>=qLeft) update(st[root].left, left, mid, qLeft, qRight, nValue);
	if (mid+1<=qRight) update(st[root].right, mid+1, right, qLeft, qRight, nValue);
	st[root].sum=st[ st[root].left ].sum + st[ st[root].right ].sum;
	return;
}
 
int n;
 
void solve() {
	st[0].l=1, st[0].r=1e9;
	int q; cin >> q;
	int c=0;
	while (q--) {
		int type; cin >> type;
		int a, b; cin >> a >> b;
		a+=c, b+=c;
		if (type==1) {
			cout << (c=query(0, 1, (int)1e9, a, b)) << endl;
		} else {
			update(0, 1, (int)1e9, a, b, 1);
		}
	}
	return;
}
 
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	75608 KB	Output is correct
2	Correct	15 ms	75408 KB	Output is correct
3	Correct	16 ms	75352 KB	Output is correct
4	Correct	28 ms	75620 KB	Output is correct
5	Correct	32 ms	75608 KB	Output is correct
6	Correct	31 ms	75616 KB	Output is correct
7	Correct	32 ms	75608 KB	Output is correct
8	Correct	142 ms	75956 KB	Output is correct
9	Correct	294 ms	75972 KB	Output is correct
10	Correct	251 ms	75912 KB	Output is correct
11	Runtime error	336 ms	153184 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-