답안 #915780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915780	2024-01-24T17:14:04 Z	Nonoze	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	562 ms	216072 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)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;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	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	-