Submission #915781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915781	2024-01-24T17:16:40 Z	Nonoze	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	452 ms	219444 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
{
	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;
	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;
	}
	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;
	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)1e7};
	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)1e7, a, b)) << endl;
		} else {
			update(root, 1, (int)1e7, 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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	20 ms	11320 KB	Output is correct
5	Correct	24 ms	13660 KB	Output is correct
6	Correct	24 ms	13120 KB	Output is correct
7	Correct	24 ms	13652 KB	Output is correct
8	Correct	190 ms	102360 KB	Output is correct
9	Correct	395 ms	174220 KB	Output is correct
10	Correct	430 ms	195408 KB	Output is correct
11	Correct	424 ms	212248 KB	Output is correct
12	Correct	452 ms	219444 KB	Output is correct
13	Incorrect	82 ms	4436 KB	Output isn't correct
14	Halted	0 ms	0 KB	-