Submission #915779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915779	2024-01-24T17:13:45 Z	Nonoze	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	581 ms	215888 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, 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)1e7};
	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;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	22 ms	11356 KB	Output is correct
5	Correct	27 ms	13660 KB	Output is correct
6	Correct	27 ms	13144 KB	Output is correct
7	Correct	27 ms	13648 KB	Output is correct
8	Correct	232 ms	100872 KB	Output is correct
9	Correct	485 ms	171076 KB	Output is correct
10	Correct	554 ms	192216 KB	Output is correct
11	Correct	555 ms	208984 KB	Output is correct
12	Correct	581 ms	215888 KB	Output is correct
13	Incorrect	126 ms	38744 KB	Output isn't correct
14	Halted	0 ms	0 KB	-