Submission #302007

#	Time	Username	Problem	Language	Result	Execution time	Memory
302007		kostia244	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2117 ms	23384 KiB

elephants

#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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3