제출 #151337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151337		GioChkhaidze	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5468 ms	15208 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int Na=150006;
const int Nq=400;

int n,m,Ms,l,Updcnt,A[Na];

int Lmax[Nq][3*Nq];
int Llen[Nq][3*Nq];

vector < int > v[Nq];

void process_block(int x) {
	int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
	
	for (int i=v[x].size()-1; i>=0; i--) {
		int pos=v[x][i];
		if (pos+l>=v[x][r]) {
			Lmax[x][i]=pos+l;
			Llen[x][i]=1;
		}
			else  {
			while (0<r && pos+l<v[x][r-1]) 
				r--;
			Lmax[x][i]=Lmax[x][r];
			Llen[x][i]=Llen[x][r]+1;
		}
	}
}

int get_ans() {
	int res=0,cur_block=0;
	
	while (cur_block<Ms && !v[cur_block].size())
		cur_block++;
	
	int pos=v[cur_block][0],idx=0;
	
	while (cur_block<Ms) {
		int Lmx=Lmax[cur_block][idx];
		res+=Llen[cur_block][idx];
	
		while (cur_block<Ms) {
			cur_block++;
			if (!v[cur_block].size()) continue;
			if (Lmx<v[cur_block][v[cur_block].size()-1]) {
				int l=0,r=v[cur_block].size()-1,mid;
				
				while (l<=r) {
					mid=(l+r)/2;
					
					if (Lmx<v[cur_block][mid]) { idx=mid; r=mid-1; }
									   				 	   else l=mid+1;
				}

				break;
			}
		}	
	}
	
	return res;
}

void restart() {
	vector < int > h;
	
	for (int i=0; i<Ms; i++) {
		for (int j=0; j<v[i].size(); j++) 
			h.push_back(v[i][j]);
			v[i].clear();
	}
	
	for (int i=0; i<h.size(); i++) 
		v[i/m].push_back(h[i]);
	
	for (int i=0; i<Ms; i++)
		process_block(i);
}

void del(int x) {
	int cur_block=-1;
	
	while (cur_block<Ms) {
		cur_block++;
		if (!v[cur_block].size()) continue;
		if (v[cur_block][v[cur_block].size()-1]<x) continue;
		
		for (int j=0; j<v[cur_block].size(); j++) 
			if (v[cur_block][j]==x)  {
				v[cur_block].erase(v[cur_block].begin()+j);
				break;	
			}
		
		break;
	}
	
	process_block(cur_block);
}

void ins(int x) {
	int cur_block=-1;
	
	while (cur_block<Ms) {
		cur_block++;
		if (!v[cur_block].size()) continue;
		if (v[cur_block][v[cur_block].size()-1]<=x) continue;
		
		for (int j=0; j<v[cur_block].size(); j++) 
			if (x<v[cur_block][j]) {
				v[cur_block].insert(v[cur_block].begin()+j,x);
				break;	
			}
		
		break;
	}
	
	if (cur_block==Ms) {
		cur_block--;
		v[cur_block].push_back(x);
	}
	
	process_block(cur_block);
}

int update(int id, int nv) {
	del(A[id]);
	A[id]=nv;
	ins(A[id]);
	Updcnt++;
	
	if (!(Updcnt%m)) restart();

    return get_ans();
}

void init(int nn, int ll, int xs[]) {
	n=nn,l=ll;
	
	m=sqrt(n);
	m+=(m*m!=n);
	Ms=(n+m-1)/m;
	
	for (int i=0; i<n; i++) {
		A[i]=xs[i];
		v[i/m].push_back(A[i]);
	}
	
	for (int i=0; i<Ms; i++) 
		process_block(i);

    return;
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void process_block(int)':
elephants.cpp:17:22: warning: unused variable 'rmax' [-Wunused-variable]
  int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
                      ^~~~
elephants.cpp: In function 'int get_ans()':
elephants.cpp:40:6: warning: unused variable 'pos' [-Wunused-variable]
  int pos=v[cur_block][0],idx=0;
      ^~~
elephants.cpp: In function 'void restart()':
elephants.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[i].size(); j++) 
                 ~^~~~~~~~~~~~
elephants.cpp:71:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j=0; j<v[i].size(); j++) 
   ^~~
elephants.cpp:73:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    v[i].clear();
    ^
elephants.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<h.size(); i++) 
                ~^~~~~~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~

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