Submission #207732

#	Time	Username	Problem	Language	Result	Execution time	Memory
207732		cgiosy	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	3921 ms	7800 KiB

elephants

#include <bits/stdc++.h>
#define lb(a, x) lower_bound(begin(a), end(a), x)
using namespace std;
constexpr int MX=150000, B=384, C=(MX+B-1)/B;

struct iii { int x, n, y; };
bool operator<(const iii& a, int b) { return a.x<b; }
bool operator<(int a, const iii& b) { return a<b.x; }
int A[MX], X[MX], N, M, Q;
vector<iii> D[C];
void calc_bucket(vector<iii>& v) {
	for(int n=v.size(), i=n, p=n; i--;) {
		while(p && v[i].x<v[p-1].x-M) p--;
		if(p==n) v[i].n=1, v[i].y=v[i].x+M;
		else v[i].n=v[p].n+1, v[i].y=v[p].y;
	}
}
void init_buckets() {
	int k=0;
	for(auto&v:D) {
		for(auto[x,n,y]:v) X[k++]=x;
		v.clear();
	}
	for(int i=0, j=0; i<N;) {
		D[j].push_back({X[i], 0, 0});
		if(++i%B==0 || i==N) calc_bucket(D[j++]);
	}
}
void del(int x) {
	for(auto&v:D) if(v.size() && v.front().x<=x && x<=v.back().x) {
		v.erase(lb(v, x));
		calc_bucket(v);
		break;
	}
}
void add(int x) {
	int p=0, n=N-1;
	for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
		v.insert(lb(v, x), {x, 0, 0});
		calc_bucket(v);
		break;
	}
}
int answer() {
	int p=0, n=0;
	for(auto&v:D) if(v.size() && p<=v.back().x) {
		auto[x,m,y]=*lb(v, p);
		n+=m, p=y+1;
	}
	return n;
}

void init(int n, int m, int E[]) {
	N=n, M=m;
	for(int i=0; i<C; i++) D[i].reserve(B);
	for(int i=0; i<N; i++) D[i/B].push_back({A[i]=E[i], 0, 0});
}
int update(int n, int x) {
	if(Q++%B==0) init_buckets();
	del(A[n]);
	add(A[n]=x);
	return answer();
}

Compilation message (stderr)

elephants.cpp: In function 'void init_buckets()':
elephants.cpp:21:17: warning: unused variable 'n' [-Wunused-variable]
   for(auto[x,n,y]:v) X[k++]=x;
                 ^
elephants.cpp:21:17: warning: unused variable 'y' [-Wunused-variable]
elephants.cpp: In function 'void add(int)':
elephants.cpp:38:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
                                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int answer()':
elephants.cpp:47:13: warning: unused variable 'x' [-Wunused-variable]
   auto[x,m,y]=*lb(v, p);
             ^

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