Submission #915780

# Submission time Handle Problem Language Result Execution time Memory
915780 2024-01-24T17:14:04 Z Nonoze Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
562 ms 216072 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, 0, -1, -1};
				root->right = new node{NULL, NULL, 0, 0, -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=query(root->left, left, mid, qLeft, qRight);
	int 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;
	update(root->left, left, mid, qLeft, qRight, nValue);
	update(root->right, mid+1, right, qLeft, qRight, nValue);
	root->update();
	return;
}

void destroy(node *root) {
	if (root->left) destroy(root->left);
	if (root->right) destroy(root->right);
	delete root;
}

int n;

void solve() {
	node* root=new node{NULL, NULL, 0, 0, 1, (int)1e8};
	int q; cin >> q;
	int c=0;
	while (q--) {
		int type; cin >> type;
		if (type==1) {
			int a, b; cin >> a >> b;
			a+=c, b+=c;
			c=query(root, 1, (int)1e8, a, b);
			cout << c << endl;
		} else {
			int a, b; cin >> a >> b;
			a+=c, b+=c;
			update(root, 1, (int)1e8, a, b, 1);
		}
	}
	destroy(root);
	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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 22 ms 11356 KB Output is correct
5 Correct 32 ms 13648 KB Output is correct
6 Correct 26 ms 13148 KB Output is correct
7 Correct 29 ms 13660 KB Output is correct
8 Correct 246 ms 100792 KB Output is correct
9 Correct 483 ms 170980 KB Output is correct
10 Correct 562 ms 192028 KB Output is correct
11 Correct 553 ms 208888 KB Output is correct
12 Correct 553 ms 216072 KB Output is correct
13 Incorrect 129 ms 38736 KB Output isn't correct
14 Halted 0 ms 0 KB -