제출 #348689

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

elephants

#include "elephants.h"
#include "bits/stdc++.h"
#define MAXN 150009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,l,arr[MAXN],asked=1,cur;
int sz[MAXN],where[MAXN];
PII tmp[MAXN];
const int BLOK=500;
vector<PII>dp[MAXN/BLOK+3],s[MAXN/BLOK+3];
void build(int block){
	int p=sz[block]-1;
	for(int i=sz[block]-1;i>=0;i--){
		while(s[block][i].ff+l<s[block][p].ff)p--;
		if(p+1<sz[block])dp[block][i]=mp(dp[block][p+1].ff+1,dp[block][p+1].ss);
		else dp[block][i]=mp(0,i);
	}
}
int query(){
	int last=-1,ans=0;
	for(int i=0;i<cur;i++)
		if(sz[i]){
			int pos=upper_bound(all(s[i]),mp(last,INF))-s[i].begin();
			if(pos<sz[i]){
				if(dp[i][pos].ff)
					ans+=dp[i][pos].ff,pos=dp[i][pos].ss;
				last=s[i][pos].ff+l;ans++;	
			}
		}
	return ans;
}
void init(int N, int L, int X[]){
	for(int i=0;i<cur;i++)
		s[i].clear(),sz[i]=0;
  	n = N; l = L; cur=0;
  	for(int i=0;i<n;i++){
  		arr[i]=X[i];
		tmp[i]=mp(X[i],i);
	}
  	sort(tmp,tmp+N);
	for(int i=0;i<n;i++){
		where[tmp[i].ss]=cur;
		s[cur].pb(tmp[i]);
		sz[cur]++;
		if((i+1)%BLOK==0)
			cur++;
	}if(n%BLOK!=0)cur++;
	for(int i=0;i<cur;i++){
		dp[i].resize(sz[i]);
		build(i);
	}
}
void rem(int block,PII val){
	for(int i=0;i<int(s[block].size());i++)
		if(s[block][i]==val){
			s[block].erase(s[block].end()-(sz[block]-i));
			break;
		}
	sz[block]--;dp[block].ppb();
	build(block);
}
void add(int block){
	sz[block]++;dp[block].pb(mp(-1,-1));
	for(int i=sz[block]-1;i>0;i--)
		if(s[block][i].ff<s[block][i-1].ff)
			swap(s[block][i],s[block][i-1]);
	build(block);
}
int update(int pos, int val){
	if(asked%BLOK==0){
		init(n,l,arr);
		asked=0;
	}asked++;
	rem(where[pos],mp(arr[pos],pos));
	arr[pos]=val;
	for(int i=0;i+1<cur;i++)
		if(s[i+1].size() and s[i+1][0].ff>val){
			s[i].pb(mp(val,pos));where[pos]=i;add(i);
			return query();
		}
	s[cur-1].pb(mp(val,pos));where[pos]=cur-1;add(cur-1);
	return query();
}

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