Submission #402931

#	Time	Username	Problem	Language	Result	Execution time	Memory
402931		Antekb	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	8996 ms	12224 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

int n, l;
vector<int> pocz;
vector<vector<int> > V;
vector<vector<int> > gdzie, ile;
vector<int> pos;
const int K=300;
void init(int N, int L, int X[])
{
	n = N;
	l=L;
	pos.resize(n);

	for(int i=0; i<n; i++){
		pos[i]=X[i];
	}
}
int cnt=0;
int find(int x){
	return max(0, (int)(upper_bound(pocz.begin(), pocz.end(), x)-pocz.begin()-1));
}
void build(int x){
	//cout<<x<<"a\n";
	if(!V[x].size())return;
	//sort(V[x].begin(), V[x].end());
	pocz[x]=V[x][0];
	gdzie[x].resize(V[x].size());
	ile[x].resize(V[x].size());
	int t=V[x].size();
	for(int i=V[x].size()-1; i>=0; i--){
		while(V[x][t-1]>V[x][i]+l)t--;
		if(t==V[x].size()){
			ile[x][i]=1;
			gdzie[x][i]=V[x][i]+l;
		}
		else{
			ile[x][i]=ile[x][t]+1;
			gdzie[x][i]=gdzie[x][t];
		}
		//cout<<i<<" "<<V[x][i]<<" "<<t<<" "<<gdzie[x][i]<<" "<<ile[x][i]<<"\n";
	}
}
void usun(int k, int x){
	vector<int> V2;
	for(int i=0; i<V[k].size(); i++){
		if(V[k][i]==x){
			x=-1;
			continue;
		}
		V2.pb(V[k][i]);
	}
	V[k]=V2;
	build(k);
}
void dodaj(int k, int x){
	vector<int> V2;
	bool b=0;
	for(int i=0; i<V[k].size(); i++){
		if(!b && V[k][i]>x){
			V2.pb(x);
			b=1;
		}
		V2.pb(V[k][i]);
	}
	if(!b){
		V2.pb(x);
	}
	V[k]=V2;
	build(k);
}
int query(){
	/*for(int i=0; i<V.size(); i++){
		cout<<pocz[i]<<"\n";
		for(int j=0; j<V[i].size(); j++){
			cout<<V[i][j]<<" "<<ile[i][j]<<" "<<gdzie[i][j]<<"\n";
		}
	}*/
	int ans=0;
	int akt=-1;
	for(int i=0; i<V.size(); i++){
		if(!V[i].size() || akt>=V[i].back())continue;
		else{
			int j=upper_bound(V[i].begin(), V[i].end(), akt)-V[i].begin();
			ans+=ile[i][j];
			akt=gdzie[i][j];
		}
	}
	return ans;
}
int update(int i, int y)
{
	if(cnt%K==0){
		V.resize((n+K-1)/K);
		gdzie.resize((n+K-1)/K);
		ile.resize((n+K-1)/K);
		pocz.resize((n+K-1)/K);
		vector<int> pos2=pos;
		sort(pos2.begin(), pos2.end());
		for(int i=0; i<V.size(); i++)V[i].clear();
		for(int i=0; i<n; i++){
			V[i/K].pb(pos2[i]);
		}
		for(int i=0; i<V.size(); i++)build(i);
	}
	/*cout<<V.size()<<"\n";
	for(int i=0; i<V.size(); i++){
		cout<<pocz[i]<<" "<<V[i].size()<<"\n";
	}*/
	int t=find(pos[i]);
	//cout<<t<<"\n";
	usun(t, pos[i]);
	pos[i]=y;
	t=find(pos[i]);
	//cout<<t<<"\n";
	dodaj(t, pos[i]);
	cnt++;
	return query();
}

Compilation message (stderr)

elephants.cpp: In function 'void build(int)':
elephants.cpp:39:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(t==V[x].size()){
      |      ~^~~~~~~~~~~~~
elephants.cpp: In function 'void usun(int, int)':
elephants.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0; i<V[k].size(); i++){
      |               ~^~~~~~~~~~~~
elephants.cpp: In function 'void dodaj(int, int)':
elephants.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0; i<V[k].size(); i++){
      |               ~^~~~~~~~~~~~
elephants.cpp: In function 'int query()':
elephants.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i=0; i<V.size(); i++)V[i].clear();
      |                ~^~~~~~~~~
elephants.cpp:110:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i=0; i<V.size(); i++)build(i);
      |                ~^~~~~~~~~

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