Submission #349611

#	Time	Username	Problem	Language	Result	Execution time	Memory
349611		amunduzbaev	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	5583 ms	14812 KiB

elephants

#include "elephants.h"
 
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int NN = 2e5+5;
const int B = 1000;
 
int n, a[NN], l, cur;
int sz[NN], bb[NN], asked;
pii tmp[NN];
vpii dp[B], s[B];

void build(int b){
	int last = sz[b] -1;
	for(int i=sz[b]-1;i>=0;i--){
		while(s[b][i].ff +l < s[b][last].ff && last >= i) last--;
		if(last < sz[b]-1) dp[b][i] = {dp[b][last+1].ff+1, dp[b][last+1].ss};
		else dp[b][i] = {0, i};
	}
}

void init(int N, int L, int X[]){
	n = N, l = L;
	for(int i=0;i<cur;i++){
		s[i].clear();
		sz[i] = 0;
	}
	for(int i=0;i<n;i++){
		tmp[i] = {X[i], i};
		a[i] = X[i];
	}
	sort(tmp, tmp+n);
	cur = 0;
	for(int i=0;i<n;i++){
		bb[tmp[i].ss] = cur;
		s[cur].pb(tmp[i]);
		sz[cur]++;
		if(sz[cur] == B) cur++;
	}
	if(sz[cur]) cur++;
	for(int i=0;i<cur;i++){
		dp[i].resize(sz[i]);
		build(i);
	}
}

void rem(int b, pii val){
	int i=0;
	while(s[b][i] != val) i++;
	s[b].erase(s[b].begin() + i);
	sz[b]--;
	dp[b].resize(sz[b]);
	build(b);
}

void sett(int b, pii val){
	s[b].pb(val);
	sz[b]++;
	dp[b].resize(sz[b]);
	bb[val.ss] = b;
	int i = sz[b]-1;
	
	while(i > 0 && s[b][i].ff < s[b][i-1].ff) { swap(s[b][i], s[b][i-1]); i--; }
	build(b);
}

int qq(){
	int last = -1, ans = 0;
	for(int i=0;i<cur;i++){
		if(sz[i]){
			auto pp = ub(all(s[i]), (pii)mp(last, mod)) - s[i].begin();
			if(pp < sz[i]){
				if(dp[i][pp].ff) ans += dp[i][pp].ff, pp = dp[i][pp].ss; 
				last = s[i][pp].ff+l, ans++;
			}
		}
	}return ans;
}
 
int update(int i, int nw){
	if(asked && asked%B == 0) { init(n, l, a); asked = 0; }
	asked++;
	
	rem(bb[i], mp(a[i], i));
	a[i] = nw;
	for(int b = 0; b+1 < cur; b++){
		if(sz[b+1] && s[b+1][0].ff > nw){
			sett(b, {a[i], i});
			//int ans = qq();
			return qq();
		}
	}
	sett(cur-1, {a[i], i});
	//int ans = qq();
	return qq();;
}

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