oj.uz

Submission #302007

# Submission time Handle Problem Language Result Execution time Memory
302007 2020-09-18T11:11:10 Z kostia244 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2117 ms 23384 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 151000, C = 512;
struct node {
	node *l, *r, *p, *pp;
	int val, sum;
	node(int x = 0) : l(0), r(0), p(0), pp(0), val(x), sum(x) {}
};
using pnode = node*;

void upd(pnode v) {
	if(!v) return;
	v->sum = v->val;
	for(auto i : {v->l, v->r}) if(i) {
		i->p = v;
		v->sum += i->sum;
	}
}

void rotate(pnode v) {
	auto p = v->p, g = p->p;
	if(g) (g->l == p ? g->l : g->r) = v;
	else v->p = 0;
	if(p->l == v)
		p->l = v->r, v->r = p;
	else
		p->r = v->l, v->l = p;
	upd(p), upd(v), upd(g);
}
pnode splay(pnode v) {
	if(!v) return 0;
	while(v->p) {
		auto p = v->p, g = p->p;
		if(g)
			rotate((g->l == p) == (p->l == v) ? p : v);
		rotate(v);
	}
	return v;
}
pnode left(pnode v) {
	splay(v);
	while(v->l) v = v->l;
	return splay(v);
}
void cut_r(pnode v) {
	splay(v);
	if(!v->r) return;
	auto t = v->r;
	t->p = v->r = 0;
	upd(v);
	t = left(t);
	t->pp = v;
}
pnode merge(pnode a, pnode b) {
	if(!a||!b) return a?:b;
	b = left(b);
	b->l = a;
	b->pp = 0;
	upd(b);
	return a;
}
void expose(pnode v) {
	cut_r(v);
	v = left(v);
	while(v->pp) {
		cut_r(v->pp);
		v = left(merge(v->pp, v));
	}
}
pnode root(pnode a) {
	expose(a);
	return left(a);
}
void link(pnode a, pnode b) {
	assert(root(a) != root(b));
	expose(b);
	a->pp = b;
}
void cut(pnode a, pnode b) {
	expose(b);
	a->pp = 0;
}
pnode lca(pnode a, pnode b) {
	expose(a);
	if(left(a)->val == left(b)->val) return b;
	expose(b);
	if(left(a)->val == left(b)->val) return a;
	return left(a)->pp;
}
deque<node> buffer;
pnode newnode(int x = 0) {
	buffer.emplace_back(x);
	return &buffer.back();
}
int n, l;
pnode nd[maxn];
int pos[maxn], curp[maxn];
set<array<int, 2>> f;

int next(int v) {
	auto it = f.upper_bound({pos[v], v});
	return it==f.end()?-1:it->at(1);
}
int jump(int v) {
	auto it = f.upper_bound({pos[v]+l, 1<<30});
	return it==f.end()?-1:it->at(1);
}
void kill(int v) {
	if(curp[v] != -1) {
		if(curp[v] != -1)
			cut(nd[v], nd[curp[v]]);
		nd[v]->val = 0;
		upd(nd[v]);
		curp[v] = -1;
	}
}

void make_link(int v) {
	kill(v);
	int x = next(v);
	int y = jump(v);
	if(x == -1)
		return;
	if(jump(x) == y) {
		//cout << v << " points(0) to " << x << " | " << pos[v] << " " << pos[x] << endl;
		link(nd[v], nd[x]);
		curp[v] = x;
	} else if(y != -1) {
		//cout << v << " points(1) to " << y << " | " << pos[v] << " " << pos[y] << endl;
		link(nd[v], nd[y]);
		curp[v] = y;
		nd[v]->val = 1;
		upd(nd[v]);
	}
}

void init(int N, int L, int X[]) {
	n = N, l = L;
	for(int i = 0; i < n; i++) {
		f.insert({X[i], i});
		pos[i] = X[i];
		curp[i] = -1;
		nd[i] = newnode(0);
	}
	for(int i = 0; i < n; i++) make_link(i);
}
void event(int x, int y) {
	auto P = f.lower_bound({x, y});
	if(P != f.begin()) {
		P--;
		make_link(P->at(1));
	}
	P = f.lower_bound({x-l, -1});
	if(P != f.begin()) {
		P--;
		make_link(P->at(1));
	}
}
int update(int i, int y) {
	//cout << "Query\n";
	auto V = f.lower_bound({pos[i], i});
	kill(i);
	f.erase({pos[i], i});
	event(pos[i], i);
	f.insert({pos[i] = y, i});
	event(y, i);
	make_link(i);
	//for(int i = 0; i < n; i++) cout << pos[i] << " " << jump(i) << '\n';
	return 1+root(nd[f.begin()->at(1)])->sum;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:162:7: warning: variable 'V' set but not used [-Wunused-but-set-variable]
  162 |  auto V = f.lower_bound({pos[i], i});
      |       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 176 ms 3200 KB Output is correct
8 Correct 187 ms 3832 KB Output is correct
9 Correct 350 ms 7968 KB Output is correct
10 Correct 184 ms 7680 KB Output is correct
11 Correct 205 ms 7688 KB Output is correct
12 Correct 543 ms 7800 KB Output is correct
13 Correct 188 ms 7544 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 176 ms 3200 KB Output is correct
8 Correct 187 ms 3832 KB Output is correct
9 Correct 350 ms 7968 KB Output is correct
10 Correct 184 ms 7680 KB Output is correct
11 Correct 205 ms 7688 KB Output is correct
12 Correct 543 ms 7800 KB Output is correct
13 Correct 188 ms 7544 KB Output is correct
14 Correct 370 ms 4708 KB Output is correct
15 Correct 352 ms 5112 KB Output is correct
16 Correct 745 ms 8456 KB Output is correct
17 Correct 830 ms 10924 KB Output is correct
18 Correct 867 ms 10752 KB Output is correct
19 Correct 232 ms 11000 KB Output is correct
20 Correct 823 ms 10820 KB Output is correct
21 Correct 842 ms 10792 KB Output is correct
22 Correct 276 ms 10388 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 176 ms 3200 KB Output is correct
8 Correct 187 ms 3832 KB Output is correct
9 Correct 350 ms 7968 KB Output is correct
10 Correct 184 ms 7680 KB Output is correct
11 Correct 205 ms 7688 KB Output is correct
12 Correct 543 ms 7800 KB Output is correct
13 Correct 188 ms 7544 KB Output is correct
14 Correct 370 ms 4708 KB Output is correct
15 Correct 352 ms 5112 KB Output is correct
16 Correct 745 ms 8456 KB Output is correct
17 Correct 830 ms 10924 KB Output is correct
18 Correct 867 ms 10752 KB Output is correct
19 Correct 232 ms 11000 KB Output is correct
20 Correct 823 ms 10820 KB Output is correct
21 Correct 842 ms 10792 KB Output is correct
22 Correct 276 ms 10388 KB Output is correct
23 Correct 1375 ms 23380 KB Output is correct
24 Correct 1399 ms 23292 KB Output is correct
25 Correct 1181 ms 23376 KB Output is correct
26 Correct 622 ms 23384 KB Output is correct
27 Correct 559 ms 23224 KB Output is correct
28 Correct 1186 ms 5496 KB Output is correct
29 Correct 1185 ms 5584 KB Output is correct
30 Correct 1181 ms 5588 KB Output is correct
31 Correct 1201 ms 5580 KB Output is correct
32 Correct 599 ms 22840 KB Output is correct
33 Correct 563 ms 22136 KB Output is correct
34 Correct 567 ms 22904 KB Output is correct
35 Correct 562 ms 23288 KB Output is correct
36 Correct 1081 ms 22776 KB Output is correct
37 Correct 1719 ms 23164 KB Output is correct
38 Correct 633 ms 22008 KB Output is correct
39 Correct 540 ms 23040 KB Output is correct
40 Correct 609 ms 22140 KB Output is correct
41 Correct 2105 ms 22904 KB Output is correct
42 Correct 2117 ms 23160 KB Output is correct