Submission #915792

# Submission time Handle Problem Language Result Execution time Memory
915792 2024-01-24T17:34:47 Z Nonoze Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
454 ms 262144 KB
#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
{
	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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 29 ms 8516 KB Output is correct
5 Correct 24 ms 10332 KB Output is correct
6 Correct 23 ms 10064 KB Output is correct
7 Correct 27 ms 10332 KB Output is correct
8 Correct 207 ms 77008 KB Output is correct
9 Correct 388 ms 130824 KB Output is correct
10 Correct 399 ms 146776 KB Output is correct
11 Correct 412 ms 159416 KB Output is correct
12 Correct 454 ms 165172 KB Output is correct
13 Correct 404 ms 205104 KB Output is correct
14 Correct 397 ms 209392 KB Output is correct
15 Runtime error 406 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -