제출 #104650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104650		figter001	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	97 / 100	9028 ms	13972 KiB

elephants

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int nax = 2e5;
const int bax = 400;

int n,l,Z = 650,cnt;
vector<pair<int,int>> a;
int p[nax],id[nax];

struct node{
	int val,id,nxt,cnt;
};
vector<node> b[bax];

void build(){
	vector<pair<int,int>> a = ::a;
	sort(a.begin(),a.end());
	int at = -1;
	int to = (n+Z-1)/Z;
	for(int i=0;i<to;i++)
		b[i].clear();
	for(int i=0;i<n;i++){
		int cur = a[i].first;
		while(at < i && cur - a[at+1].first > l)
			at++;
		id[a[i].second] = i/Z;
		if(at == -1 || at/Z != i/Z)
			b[i/Z].push_back({cur,a[i].second,cur - l,1});
		else
			b[i/Z].push_back({cur,a[i].second,b[at/Z][at%Z].nxt,b[at/Z][at%Z].cnt + 1});
	}
}

void rem(int bucket,int val){
	vector<pair<int,int>> tmp;
	for(int i=0;i<b[bucket].size();i++){
		if(b[bucket][i].id == val)
			continue;
		tmp.push_back({b[bucket][i].val,b[bucket][i].id});
	}
	b[bucket].clear();
	int at = -1;
	for(int i=0;i<tmp.size();i++){
		int cur = tmp[i].first;
		while(at < i && cur - tmp[at+1].first > l)
			at++;
		if(at == -1)
			b[bucket].push_back({cur,tmp[i].second,cur - l,1});
		else
			b[bucket].push_back({cur,tmp[i].second,b[bucket][at].nxt,b[bucket][at].cnt + 1});
	}
}

void add(int val,int x){
	int to = (n+Z-1)/Z;
	int bucket = to - 1;
	for(int i=0;i<to;i++){
		if(b[i].size() && val <= b[i].back().val){
			bucket = i;
			break;
		}
	}
	id[x] = bucket;
	vector<pair<int,int>> tmp;
	bool ad = 0;
	for(int i=0;i<b[bucket].size();i++){
		if(b[bucket][i].val >= val && !ad){
			tmp.push_back({val,x});
			ad = 1;
		}
		tmp.push_back({b[bucket][i].val,b[bucket][i].id});
	}
	if(!ad)
		tmp.push_back({val,x});
	b[bucket].clear();
	int at = -1;
	for(int i=0;i<tmp.size();i++){
		int cur = tmp[i].first;
		while(at < i && cur - tmp[at+1].first > l)
			at++;
		if(at == -1)
			b[bucket].push_back({cur,tmp[i].second,cur - l,1});
		else
			b[bucket].push_back({cur,tmp[i].second,b[bucket][at].nxt,b[bucket][at].cnt + 1});
	}
}

void init(int N, int L, int X[]){
	n = N;
	// Z = sqrt(n) + 1;
	l=L;
	for(int i=0;i<n;i++){
		a.push_back({X[i],i});
		p[i] = X[i];
	}
	build();
}

int update(int x, int y){
	if(cnt == Z - 2){
		build();
		cnt = 0;
	}
	cnt++;
	int curbucket = id[x];
	a[x].first = y;
	rem(curbucket,x);
	add(y,x);

	int ans = 0;

	int cur = (n+Z-1)/Z - 1;
	while(cur >= 0 && b[cur].size() == 0)
		cur--;
	int at = b[cur].size() - 1;

	for(int i=cur;i>=0;i--){
		ans += b[i][at].cnt;
		int to = b[i][at].nxt;
		if(i == 0)
			break;
		while(1){
			if(i == 0)
				break;
			int small = (int)2e9;
			if(b[i-1].size())
				small = b[i-1][0].val;
			if(small >= to)
				i--;
			else
				break;
		}
		if(i == 0)
			break;
		int md,lo=0,hi=b[i-1].size()-1;
		at = -1;
		while(lo <= hi){
			md = (lo + hi)/2;
			if(b[i-1][md].val < to){
				lo = md+1;
				at = md;
			}else hi = md-1;
		}
	}
	return ans;
}

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

elephants.cpp: In function 'void rem(int, int)':
elephants.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
              ~^~~~~~~~~~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
              ~^~~~~~~~~~~

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