Submission #406232

#	Time	Username	Problem	Language	Result	Execution time	Memory
406232		pure_mem	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9045 ms	12644 KiB

elephants

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

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 150000, BS = 300, INF = 1e9 + 7;

int n, w, p[MAXN], ps[MAXN], buck[MAXN];
vector< pair< int, int > > bl[MAXN / BS + 3];
int dp1[MAXN], dp2[MAXN];

void trick(vector< pair<int, int> > &cur, pair<int, int> val){
	vector< pair<int, int> > tmp;
	for(pair<int, int> v: cur){
		if(val == v)
			continue;
		tmp.push_back(v);
	}
	cur.swap(tmp), tmp.clear();
}

void upd(int id, bool keep = 0){		
	if(!keep)
		sort(bl[id].begin(), bl[id].end());
	for(int i = (int)bl[id].size() - 1, j = (int)bl[id].size();i >= 0;i--){
		int me = bl[id][i].Y, pos = bl[id][i].X;
		buck[me] = id;
		while(j - 1 >= i && bl[id][j - 1].X > pos + w) j--;
		if(j == (int)bl[id].size()) dp1[me] = 1, dp2[me] = pos + w;
		else dp1[me] = dp1[bl[id][j].Y] + 1, dp2[me] = dp2[bl[id][j].Y]; 	
	}		
}

void build(){		
	sort(ps, ps + n, [](int x, int y){return p[x] < p[y];});
	for(int i = 0, j = 0;i < n;i += BS, j++)
		bl[j].clear();
	for(int i = 0, j = 0, z = 1;i < n;i++, (z == BS ? z = 1, j++: z++))
		bl[j].push_back(MP(p[ps[i]], ps[i]));
	for(int i = 0, j = 0;i < n;i += BS, j++)
		upd(j, 1);
}

void init(int N, int L, int X[]){
  	n = N, w = L;
  	for(int i = 0;i < n;i++)
    	p[i] = X[i], ps[i] = i; 
	build();
}

int solve(){
	int cnt = 0, pos = 0;
	for(int j = 0;;j++){
		if(bl[j].empty())
			break;
		else if(bl[j].back().X < pos)
			continue;
		pair<int, int> tmp = *upper_bound(bl[j].begin(), bl[j].end(), MP(pos, -1));
		cnt += dp1[tmp.Y], pos = dp2[tmp.Y] + 1;
	}	
	return cnt;
}

int cntQ;

int update(int i, int y){
  	cntQ++;
  	if(cntQ == BS){
    	p[i] = y, cntQ = 0;
    	build();
  	}
  	else{ 
  		trick(bl[buck[i]], MP(p[i], i)), upd(buck[i]);
  		p[i] = y;
  		for(int j = 0;;j++){
  			int left = (j ? bl[j - 1].back().X: 0), right = (bl[j + 1].empty() ? INF: bl[j + 1][0].X);
  			if(left <= y && y <= right){
  				bl[j].push_back(MP(y, i)), upd(j);
  				break;
  			}
  		}
  	}
  	return solve();
}

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