Submission #915788

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915788	2024-01-24T17:23:30 Z	Nonoze	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	460 ms	217028 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)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)1e8, a, b)) << endl;
		} else {
			update(root, 1, (int)1e8, 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	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	21 ms	11448 KB	Output is correct
5	Correct	25 ms	13652 KB	Output is correct
6	Correct	25 ms	13156 KB	Output is correct
7	Correct	26 ms	13668 KB	Output is correct
8	Correct	207 ms	101500 KB	Output is correct
9	Correct	423 ms	172212 KB	Output is correct
10	Correct	427 ms	193104 KB	Output is correct
11	Correct	460 ms	209676 KB	Output is correct
12	Correct	453 ms	217028 KB	Output is correct
13	Incorrect	120 ms	40016 KB	Output isn't correct
14	Halted	0 ms	0 KB	-