Submission #356228

#	Time	Username	Problem	Language	Result	Execution time	Memory
356228		tengiz05	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	6021 ms	7712 KiB

elephants

#include "elephants.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
int len, A[160001], n, a[160001];
const int BlockSize = 1000, BigSize = BlockSize*2;
int Counter, blen;
struct Block{
	int arr[BigSize], where[BigSize], pos[BigSize], need[BigSize], sz;
	int max(){return arr[sz-1];}
	int min(){return arr[0];}
	bool contain(int x){return x >= min() && x <= max();}
	void clear(){sz=0;}
	void recalc(){
		for(int i=sz-1, j=sz-1;i>=0;i--){
			int r = arr[i] + len;
			while(j>0 && arr[j-1] > r)j--;
			if(r >= max()){
				need[i] = 1;
				pos[i] = r;
			}else {
				need[i] = need[j]+1;
				pos[i] = pos[j];
			}
		}
	}
	void insert(int x){ 
		arr[sz++] = x;
		int p = sz - 1;
		while(p && arr[p]<arr[p-1])swap(arr[p], arr[p-1]), --p;
		recalc();
   	}
	void remove(int x){
		int p = 0;
		while(arr[p] < x) ++p;
		while(p+1 < sz)arr[p] = arr[p+1],p++;
		--sz;
		recalc();
	}
	void rebuild(int l, int r){
		sz = r-l;
		for(int i=0;i<sz;i++){
			arr[i] = a[l+i];
		}recalc();
	}void advance(int &r, int &cnt) {
		int p = upper_bound(arr,arr+sz, r)-arr;
		r = pos[p], cnt += need[p];
	}
}block[160000/BlockSize];

void Remove(int x){
	for(int i=0;i<blen;++i){
		if (block[i].contain(x)){
			block[i].remove(x);
			return;
		}
	}
}
void Insert(int x){
	for(int i=0;i<blen;i++){
		if (i==blen-1 || block[i+1].min()>x){
			block[i].insert(x);
			return;
		}
	}
}
int query(){
	int cur=-1, ans=0;
	for(int i=0;i<blen;i++){
		if (cur >= block[i].max())continue;
		block[i].advance(cur,ans);
	}
	return ans;
}
void init(int N, int L, int X[]){
	len = L;
	n = N;
	for(int i=0;i<N;i++)A[i] = a[i] = X[i];
	sort(a, a+n);
	for(int id=0;;id++){
		int L = id*BlockSize, R = min(n, L+BlockSize);
		block[id].rebuild(L, R);
		blen = id+1;
		if(R == n)break;
	}
}

int update(int i, int y){
	Counter++;
	if(Counter == BlockSize){
		A[i] = y;
		Counter = 0;
		init(n,len,A);
		return query();
	}
	Remove(A[i]);
	A[i] = y;
	Insert(A[i]);
	return query();
}

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