Submission #233945

#	Time	Username	Problem	Language	Result	Execution time	Memory
233945		crossing0ver	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	4991 ms	13152 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int K = 400, MXN = 1.5E5 + 5;
int P[150000], inbox[150000] , L,B = MXN/K, n,Q,sorted[150000]; 
struct BLOCK{
	int sz;
	int arr[K*2 + 10] , last[K*2 + 10], cost[K*2 + 10];
	
	void del(int x) {
		for (int i = 0; i < sz; i++)
			if (arr[i] == x) {
				x = i; break;
			}
		for (; x < sz;x++)
			swap(arr[x],arr[x+1]);
		sz--;
	}
	void insert (int x) {
		arr[sz] = x;
		int pos = sz;
		for ( ; pos > 0 && P[x] <  P[ arr[pos - 1] ]; pos--)
				swap(arr[pos],arr[pos - 1]);
		sz++;
	}
	void slv() {
		int ptr = sz - 1;
		for (int i = sz - 1; i >= 0; i--) {
			while (ptr > 0 && P[arr[i]] + L < P[arr[ptr - 1]]) ptr--;
			if (P[arr[i]] + L>= P[arr[sz - 1]]) 
					cost[i] = 1, last[i] = arr[i];
			else cost[i] = 1 + cost[ptr], last[i] = last[ptr];
		}
	}
	
	int get (int val) {
		if (sz == 0 ) return -1;
		int l = 0, r = sz - 1;
		while ( l != r) {
			int m = (l + r)/2;
			if (P[arr[m]] > val) r = m;
			else l = m + 1;
		}
		if (P[arr[r]] <= val) return -1;
		return r;
	} 
} box[MXN/K + 10];             
					  
void build() {
	if (Q % K != 0) return;
	if (Q == 0) {
		for (int i = 0; i < n; i++)
		sorted[i] = i;
	}
	else {
		int cnt = 0;
		for (int i = 0; i <= B; i++) {
			 for (int j = 0; j < box[i].sz; j++)
			 	sorted[cnt++] = box[i].arr[j];
		}		
	}
	
	for (int i = 0 ; i <= B; i++) 
	box[i].sz = 0;
	int blc = -1;
	for (int i = 0; i < n; i++) {
		if (i % K == 0){
			blc++;
			box[blc].sz = 0;
		}
		box[blc].insert(sorted[i]);
		inbox[sorted[i]] = blc;
	}
	for (int i= 0; i <= B; i++)	box[i].slv();
	B = blc + 1;
}                  


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

int update(int i, int y) {
	Q++;
	box[inbox[i]].del(i);
	box[inbox[i]].slv();
	P[i] = y;
	for (int j = 0; j <= B; j++) {
		if (((box[j+1].sz) && P[box[j+1].arr[0]] >= y) || j == B - 1) {
			box[j].insert(i);
			inbox[i] = j;
			box[j].slv();
			break;
		}
	}
	build();
	int val = INT_MIN,ans = 0;
	for (int i = 0; i <= B; i++) {
		int pos = box[i].get(val + L);
		if (pos == -1) continue;
		ans+= box[i].cost[pos];
		val = P[box[i].last[pos]];
	}    
	return ans;       
}
		   /*
int main(){
	int N,L1,q;
	cin >> N >> L1 >> q;
	int X[N];
	for (int i = 0 ; i<  N ; i ++) cin >> X[i];
	init(N,L1,X);
	while (q--) {
		int i,y;
		cin >> i >> y;
		cout << update(i,y) <<' ';
		cout << P[i] <<'\n';
	}
}         */               
/* 4 10 5 
 10 15 17 20
*/

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