Submission #402924

#	Time	Username	Problem	Language	Result	Execution time	Memory
402924		Antekb	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	1636 ms	4120 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());
	for(int i=V[x].size()-1; i>=0; i--){
		int t=upper_bound(V[x].begin(), V[x].end(), V[x][i]+l)-V[x].begin();
		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){
	V[k].pb(x);
	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(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);
	}
	/*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]<<" ";
			cout<<"\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:38:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if(t==V[x].size()){
      |      ~^~~~~~~~~~~~~
elephants.cpp: In function 'void usun(int, int)':
elephants.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0; i<V[k].size(); i++){
      |               ~^~~~~~~~~~~~
elephants.cpp: In function 'int query()':
elephants.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i=0; i<V.size(); i++)V[i].clear();
      |                ~^~~~~~~~~
elephants.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i=0; i<V.size(); i++)build(i);
      |                ~^~~~~~~~~

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