Submission #915793

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915793	2024-01-24T17:37:07 Z	Nonoze	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	395 ms	262144 KB

apple

#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;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	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	-