Submission #233917

#	Time	Username	Problem	Language	Result	Execution time	Memory
233917		crossing0ver	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	5 ms	384 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int K = 400, MXN = 1.5E5 + 5;
const int B = MXN/K + 5;
int P[150000], inbox[150000] , L, n;
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() {
	int blc = -1;
	for (int i = 0; i < n; i++) {
		if (i % K == 0){
			blc++;
		}
		box[blc].insert(i);
		inbox[i] = blc;
	}
	for (int i= 0; i <= B; i++)	box[i].slv();
	
}


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) {
	box[inbox[i]].del(i);
	box[inbox[i]].slv();
	P[i] = y;
	for (int j = 0; j <= B; j++) {
		if ((!box[j].sz || P[box[j].arr[box[j].sz - 1]] > y) || j == B) {
			box[j].insert(i),inbox[i] = j,
			box[j].slv();
			break;
		}
	}
	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++;
		val = P[box[i].last[pos]];
	}    
	return ans; 
}
			  /*
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) <<'\n';
	}
}          */
/* 4 10 5 
 10 15 17 20

 */

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