Submission #251294

#	Time	Username	Problem	Language	Result	Execution time	Memory
251294		kostia244	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	25 ms	4608 KiB

elephants

#include "elephants.h"
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,sse4.1,popcnt,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150670, C = 256;
int n, l, x[maxn], bl[maxn], to[maxn], sto[maxn], w[maxn];
#define INLINE inline __attribute__(( always_inline ))
struct costum_vec {
	int a[2*C], sz = 0;
	INLINE int& operator[] (int i) {
		return a[i];
	}
	INLINE void push_back(int x) {
		a[sz++] = x;
	}
	INLINE void pop_back() { --sz; }
	INLINE void clear() {sz = 0;}
	INLINE int size() { return sz; }
	INLINE bool empty() { return !sz; }
	INLINE int back() { return a[sz-1]; }
};
costum_vec b[maxn/C];

int fuck[maxn];
void upfuck(int i) {
	if(fuck[i] < 0) return;
	for(int j = 0; j < b[i].size(); j++) to[b[i][j]] = sto[b[i][j]] = fuck[i];
	fuck[i] = -606060;
}

INLINE int lower_bound2(int X, int LBB = 0) {
	int B = LBB, I = 0;
	if(B > maxn/C || b[B].empty()) return n;
	for(int z = 1<<11; z>>=1;) if(B+z < maxn/C && !b[B+z].empty() && x[b[B+z][0]] < X) B += z;
	for(int z = 1<<10; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
	//cout << X << " // " << B << " " << I << '\n';
	if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
	//cout << X << " // " << B << " " << I << '\n';
	//cout << "Final" << (b[B].empty() ? n : b[B][I]) << '\n';
	return b[B].empty() ? n : b[B][I];
}
INLINE int lower_bound(int X, int &B) {
	int I = 0;
	while(B < maxn/C && !b[B].empty() && x[b[B].back()] < X) B++;
	if(B >= maxn/C || b[B].empty()) return n;
	for(int z = 1<<10; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
	//cout << X << " // " << B << " " << I << '\n';
	if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
	//cout << X << " // " << B << " " << I << '\n';
	//cout << "Final" << (b[B].empty() ? n : b[B][I]) << '\n';
	return b[B].empty() ? n : b[B][I];
}
template<int init = 0>
INLINE void update(int i) {
	upfuck(i);
	//cout << "Updated block " << i << "\n";
	//for(auto v : b[i]) cout << v << " "; cout << '\n';
	if(init) {
	int f = 0;
	for(int p = 0; p < b[i].size(); p++) {
		to[b[i][p]] = lower_bound(x[b[i][p]]+l+1, f);//, cout << v << " " << x[v]+l+1 << " " << to[v] << '\n';
	}
	}
	for(int v, _v = b[i].size(); _v--;) {
		v = b[i][_v];
		if(bl[to[v]] == bl[v])
			sto[v] = sto[to[v]], w[v] = 1+w[to[v]];
		else sto[v] = v, w[v] = 1;
	}
}
void fuckonrange(int l, int r, int val) {
	//if(val > n)
	//	cout << "set " << l << " " << r << " " << val << endl;
	for(int i = 0; i*C < n; i++) if(!b[i].empty()) {
		//cout << "at least I got here\n" << " " << x[b[i].back()] << " " << x[b[i][0]] << '\n';
		if(x[b[i].back()] < l || x[b[i][0]] > r) continue;
		//cout << "at least I got here\n";
		if(x[b[i].back()] <= r && x[b[i][0]] >= l) fuck[i] = val;
		else {
		for(int j = 0; j < b[i].size(); j++)
			if(x[b[i][j]] >= l && x[b[i][j]] <= r) to[b[i][j]] = val;//, cout << "set --" << b[i][j] << '\n';
			//else cout << "Not set " << b[i][j] << " " << x[b[i][j]] << '\n';
		update(i);
		}
	}
}
INLINE void pop(int v) {
	upfuck(bl[v]);
	for(int i = 0; i+1 < b[bl[v]].size(); i++)
		if(b[bl[v]][i] == v) swap(b[bl[v]][i], b[bl[v]][i+1]);
	b[bl[v]].pop_back();
	update(bl[v]);
}
INLINE void push(int i) {
	upfuck(bl[i]);
	bl[i] = min((n-1)/C, bl[lower_bound2(x[i])]);
	int bid = bl[i];
	//for(auto &b : b[bid]) cout << x[b] << " "; cout << "F\n";
	for(int p = 0; p < b[bid].size(); p++)
		if(x[b[bid][p]] > x[i]) swap(b[bid][p], i);
	b[bid].push_back(i);
	//for(auto &b : b[bid]) cout << x[b] << " "; cout << "G\n";
	update(bid);
}
multiset<int> vals;
void removex(int f) {
	vals.erase(vals.find(f));
	auto it = vals.lower_bound(f);
	if(it == vals.begin()) return;
	auto it2 = it;--it2;
	fuckonrange(*it2-l, f-l-1, it == vals.end() ? n : lower_bound2(*it));
}
void addx(int f, int id) {
	auto it = vals.insert(f);
	auto pit = it;
	if(it != vals.begin()) {
		--pit;
		fuckonrange(*pit-l, f-l-1, id);
	}
}
int ord[maxn];
template<int init = 0>
INLINE void build() {
	memset(fuck, -1, sizeof fuck);
	int sz = 0;
	for(int i = 0; i*C < n; i++)
		for(int j = 0; j < b[i].size(); j++)
			ord[sz++] = b[i][j];
	if(init)
		for(int i = 0; i < n; i++) ord[sz++] = i, addx(x[i], i);
	for(int i = 0; i*C < n; i++) {
		b[i].clear();
		//b[i].reserve(2*C);
	}
	for(int i, pos = 0; pos < n; pos++) {
		i = ord[pos];
		bl[i] = pos/C;
		b[bl[i]].push_back(i);
	}
	for(int i = 0; i*C < n; i++) update<init>(i);
}
void init(int N, int L, int X[]) {
	//cout << L << "\n";
	n = N;
	l = L;
	bl[n] = maxn;
	for(int i = 0; i < n; i++) x[i] = X[i];
	build<1>();
}
INLINE int calc() {
	//for(auto i : vals) cout << i << " "; cout << '\n';
	//cout << fuck[2] << '\n';
	//for(int i = 0; i < 2; i++) cout << b[0][i] << " "; cout << '\n';
	//for(int i = 0; i < 2; i++) cout << to[b[0][i]] << " "; cout << '\n';
	int p = b[0][0], ans = 0, uwu = 0;
	while(p != n) {
		ans += w[p];
		p = sto[p];
		if(fuck[bl[p]]>=0) p = fuck[bl[p]];
		else p = to[p];
		//cout << p << " " << to[p] << '\n';
	}
	return ans;
}
int timer = 0;
int update(int i, int y) {
	pop(i);
	int ox = x[i];
	x[i] = y;
	to[i] = lower_bound2(x[i]+l+1);
	//cout << to[i] << "(rofl\n)";
	//cout << "Y_" << i << " := " << y << endl;
	removex(ox);
	addx(y, i);
	//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
	//	for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
	push(i);
	//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
	//	for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
	if(++timer == C-1) timer = 0, build();
	return calc();
}

Compilation message (stderr)

elephants.cpp: In function 'int calc()':
elephants.cpp:156:28: warning: unused variable 'uwu' [-Wunused-variable]
  int p = b[0][0], ans = 0, uwu = 0;
                            ^~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3