답안 #90488 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90488	2018-12-21T21:00:47 Z	radoslav11	Growing Trees (BOI11_grow)	C++14	100 / 100	597 ms	42512 KB

grow

/*
	All queries can be handled with a simple implicit treap. The complexity is O((N + M) log N).
*/

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

random_device rd;
mt19937 mt(rd());

struct node
{
	int sz, prior, value, lazy;
	node *l, *r;
	node() { lazy = 0; value = 0; sz = 0; prior = 0; l = nullptr; r = nullptr; }
	node(int v) { lazy = 0; value = v; sz = 1; prior = mt(); l = nullptr; r = nullptr; }
};

typedef node* pnode;

inline int size(pnode v) { return v ? v->sz : 0; }

void push(pnode &t)
{
	if(!t) return;
	if(t->lazy)
	{
		t->value += t->lazy;
		if(t->l) t->l->lazy += t->lazy;
		if(t->r) t->r->lazy += t->lazy;
		t->lazy = 0;
	}
}

void pull(pnode &v) 
{ 
	if(!v) return;
	push(v->l);
	push(v->r);
	v->sz = size(v->l) + size(v->r) + 1; 
}

void merge(pnode &t, pnode l, pnode r)
{
	push(l), push(r);
	if(!l) { t = r; return; }
	if(!r) { t = l; return; }

	if(l->prior > r->prior)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;

	pull(t);
}

void split(pnode t, pnode &l, pnode &r, int k)
{
	push(t);
	if(!t) { l = nullptr; r = nullptr; return; }

	if(t->value <= k)
		split(t->r, t->r, r, k), l = t;
	else
		split(t->l, l, t->l, k), r = t;

	pull(t);
}

void merge_op(pnode &t, pnode l, pnode r)
{
	push(l), push(r);
	if(!l) { t = r; return;  }
	if(!r) { t = l; return;  }

	if(l->prior < r->prior)
		swap(l, r);

	pnode L, R;
	split(r, L, R, l->value - mt() % 2);
	merge_op(l->r, l->r, R);
	merge_op(l->l, L, l->l);

	t = l;
	pull(t);
}

void split_sz(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
	push(t);
	if(!t) { l = nullptr; r = nullptr; return; }

	int idx = add + size(t->l);
	if(idx <= k)
		split_sz(t->r, t->r, r, k, idx + 1), l = t;
	else
		split_sz(t->l, l, t->l, k, add), r = t;

	pull(t);
}

pnode root;

void insert(int x)
{
	pnode l, r, v = new node(x);
	split(root, l, r, x);
	merge(l, l, v);
	merge(root, l, r);
}

void add(int h, int c)
{
	pnode L, R, mid;
	split(root, L, R, h - 1);
	split_sz(R, mid, R, c - 1);

	if(mid) mid->lazy += 1;

	merge(root, L, mid);
	merge_op(root, root, R);
}

int query(int x, int y)
{
	pnode l, r, mid;
	split(root, l, r, x - 1);
	split(r, mid, r, y);

	int ans = size(mid);

	merge(root, l, mid);
	merge(root, root, r);

	return ans;
}

int n, m;

void read()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		int h;
		cin >> h;
		insert(h);
	}
}

void solve()
{
	while(m--)
	{
		char t;
		int a1, a2;
		cin >> t >> a1 >> a2;
		if(t == 'F') add(a2, a1);
		else cout << query(a1, a2) << endl;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	416 ms	6216 KB	Output is correct
2	Correct	456 ms	7608 KB	Output is correct
3	Correct	167 ms	9032 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9032 KB	Output is correct
2	Correct	7 ms	9032 KB	Output is correct
3	Correct	7 ms	9032 KB	Output is correct
4	Correct	5 ms	9032 KB	Output is correct
5	Correct	131 ms	9032 KB	Output is correct
6	Correct	158 ms	9032 KB	Output is correct
7	Correct	15 ms	9032 KB	Output is correct
8	Correct	43 ms	9032 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	140 ms	9436 KB	Output is correct
2	Correct	155 ms	10532 KB	Output is correct
3	Correct	6 ms	10532 KB	Output is correct
4	Correct	69 ms	11312 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	12452 KB	Output is correct
2	Correct	175 ms	13288 KB	Output is correct
3	Correct	28 ms	13288 KB	Output is correct
4	Correct	158 ms	14492 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	380 ms	18092 KB	Output is correct
2	Correct	455 ms	19624 KB	Output is correct
3	Correct	57 ms	19624 KB	Output is correct
4	Correct	148 ms	21172 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	525 ms	22472 KB	Output is correct
2	Correct	485 ms	23936 KB	Output is correct
3	Correct	167 ms	25068 KB	Output is correct
4	Correct	60 ms	25068 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	363 ms	27072 KB	Output is correct
2	Correct	441 ms	28600 KB	Output is correct
3	Correct	172 ms	29624 KB	Output is correct
4	Correct	57 ms	29624 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	506 ms	32012 KB	Output is correct
2	Correct	554 ms	32816 KB	Output is correct
3	Correct	199 ms	34460 KB	Output is correct
4	Correct	230 ms	35228 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	522 ms	36428 KB	Output is correct
2	Correct	435 ms	38056 KB	Output is correct
3	Correct	597 ms	40380 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	450 ms	42512 KB	Output is correct

답안 #90488

Compilation message