Submission #416011

#	Time	Username	Problem	Language	Result	Execution time	Memory
416011		CSQ31	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	332 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef vector<vector<int>> vii;
typedef pair<int,int> pii;
int n,l;
int x[1500001];
int blk = 500;
struct bucket{
	int sz;
	int x[1001];
	int cnt[1001];
	int reach[1001];
	void calc(){
		int t = sz;
		for(int i=sz-1;i>=0;i--){
			while(t && x[t-1] > x[i]+l)t--;
			if(t == sz){
				cnt[i] = 1;
				reach[i] = x[i]+l;
			}else{
				cnt[i] = cnt[t]+1;
				reach[i] = reach[t];
				
			}
		}
		
	}
	void add(int y){
		int p = ub(x,x+sz,y) - x;
		sz++;
		for(int i=sz-1;i>p;i--)x[i] = x[i-1];
		x[p] = y;
		calc();
	}
	void del(int y){
		int p = lb(x,x+sz,y) - x;
		sz--;
		for(int i=p;i<sz;i++)x[i] = x[i+1];
		calc();
		
	}
	
}b[500];
int bcnt = 0;
void init(int N, int L, int X[])
{
	n = N;
	l = L;
	for(int i=0;i<n;i++)x[i] = X[i];
	for(int i=0;i<n;i+=blk){
		for(int j=i;j<min(i+blk,n);j++){
			b[bcnt].x[b[bcnt].sz++] = x[j];
		}
		b[bcnt++].calc();
	}
	//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
//cout<<"BUILT"<<'\n';
}
void rebuild(){
	vector<int>nx;
	for(int i=0;i<bcnt;i++){
		for(int j=0;j<b[i].sz;j++){
			nx.pb(b[i].x[j]);
		}
	}
	bcnt = 0;
	for(int i=0;i<n;i+=blk){
		b[bcnt].sz = 0;
		for(int j=i;j<min(i+blk,n);j++){
			b[bcnt].x[b[bcnt].sz++] = nx[j];
		}
		b[bcnt++].calc();
	}
}
int num = 0;
int update(int i, int y)
{
	if(num == 400){rebuild();num=0;}
	int pv = x[i];
	//cout<<"del"<<'\n';
	for(int i=0;i<bcnt;i++){
		if(b[i].x[0] <= pv && b[i].x[b[i].sz-1] >= pv){
			b[i].del(y);
			break;
		}
	}
	//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
	x[i] = y;
	for(int i=0;i<bcnt;i++){
		if((i == 0 || b[i].x[0] <= y) && (i == bcnt-1 || (b[i+1].x[0] > y))){
			b[i].add(y);
			break;
		}
	}
	//cout<<"add"<<'\n';
	//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
	int ans = 0;
	int cur = -1;
	for(int i=0;i<bcnt;i++){
		if(cur>=b[i].x[b[i].sz-1])continue;
		if(cur < b[i].x[0]){
			ans+=b[i].cnt[0];
			cur = b[i].reach[0];
			continue;
		}
		int p = ub(b[i].x,b[i].x+b[i].sz,cur) - b[i].x;
		ans+=b[i].cnt[p];
		cur=b[i].reach[p];
	}
	num++;
	return ans;
}

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