답안 #915793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915793 2024-01-24T17:37:07 Z Nonoze 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
395 ms 262144 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("O3")
//#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
{
	node* left, *right;
	int sum, lazy;
	int l, r;
	void update() {
		sum=left->sum+right->sum;
	}
};
 
void propagate(node* root, int l, int r) {
	if (root->lazy!=-1) {
		root->sum=(r-l+1)*root->lazy;
		if (l!=r)
		{
			int mid=(l+r)/2;
			if (!root->left) {
				root->left = new node{NULL, NULL, 0, -1, -1, -1};
				root->right = new node{NULL, NULL, 0, -1, -1, -1};
				root->right->l=mid+1, root->right->r=r;
				root->left->l=l, root->left->r=mid;
			}
			root->left->lazy=root->lazy;
			root->right->lazy=root->lazy;
		}
		root->lazy=-1;
	}
}
 
int query(node* 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 root->sum;
	int mid=(left+right)/2;
	int s1=0, s2=0;
	if (root->left) s1=query(root->left, left, mid, qLeft, qRight);
	if (root->right) s2=query(root->right, mid+1, right, qLeft, qRight);
	return s1+s2;
}
 
void update(node* 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) {
		root->lazy=nValue;
		propagate(root, left, right);
		return;
	}
	int mid=(left+right)/2;
	if (!root->left) {
		root->left = new node{NULL, NULL, 0, -1, -1, -1};
		root->right = new node{NULL, NULL, 0, -1, -1, -1};
		root->right->l=mid+1, root->right->r=right;
		root->left->l=left, root->left->r=mid;
	}
	update(root->left, left, mid, qLeft, qRight, nValue);
	update(root->right, mid+1, right, qLeft, qRight, nValue);
	root->update();
	return;
}
 
int n;
 
void solve() {
	node* root=new node{NULL, NULL, 0, -1, 1, (int)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(root, 1, (int)1e9, a, b)) << endl;
		} else {
			update(root, 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 18 ms 8664 KB Output is correct
5 Correct 22 ms 10356 KB Output is correct
6 Correct 22 ms 10076 KB Output is correct
7 Correct 23 ms 10324 KB Output is correct
8 Correct 174 ms 77136 KB Output is correct
9 Correct 360 ms 130896 KB Output is correct
10 Correct 394 ms 147096 KB Output is correct
11 Correct 390 ms 159312 KB Output is correct
12 Correct 389 ms 165024 KB Output is correct
13 Correct 357 ms 204980 KB Output is correct
14 Correct 358 ms 207188 KB Output is correct
15 Runtime error 395 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -