oj.uz

Submission #233946

# Submission time Handle Problem Language Result Execution time Memory
233946 2020-05-22T12:59:06 Z crossing0ver Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5025 ms 8636 KB 
#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, 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;
	}
	B = blc + 1;
	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) {
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 488 ms 1920 KB Output is correct
8 Correct 520 ms 2088 KB Output is correct
9 Correct 449 ms 3448 KB Output is correct
10 Correct 433 ms 3320 KB Output is correct
11 Correct 462 ms 3320 KB Output is correct
12 Correct 735 ms 3448 KB Output is correct
13 Correct 435 ms 3328 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 488 ms 1920 KB Output is correct
8 Correct 520 ms 2088 KB Output is correct
9 Correct 449 ms 3448 KB Output is correct
10 Correct 433 ms 3320 KB Output is correct
11 Correct 462 ms 3320 KB Output is correct
12 Correct 735 ms 3448 KB Output is correct
13 Correct 435 ms 3328 KB Output is correct
14 Correct 411 ms 2296 KB Output is correct
15 Correct 766 ms 2680 KB Output is correct
16 Correct 1283 ms 3592 KB Output is correct
17 Correct 1353 ms 4472 KB Output is correct
18 Correct 1436 ms 4344 KB Output is correct
19 Correct 769 ms 4472 KB Output is correct
20 Correct 1305 ms 4344 KB Output is correct
21 Correct 1266 ms 4472 KB Output is correct
22 Correct 739 ms 4388 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 488 ms 1920 KB Output is correct
8 Correct 520 ms 2088 KB Output is correct
9 Correct 449 ms 3448 KB Output is correct
10 Correct 433 ms 3320 KB Output is correct
11 Correct 462 ms 3320 KB Output is correct
12 Correct 735 ms 3448 KB Output is correct
13 Correct 435 ms 3328 KB Output is correct
14 Correct 411 ms 2296 KB Output is correct
15 Correct 766 ms 2680 KB Output is correct
16 Correct 1283 ms 3592 KB Output is correct
17 Correct 1353 ms 4472 KB Output is correct
18 Correct 1436 ms 4344 KB Output is correct
19 Correct 769 ms 4472 KB Output is correct
20 Correct 1305 ms 4344 KB Output is correct
21 Correct 1266 ms 4472 KB Output is correct
22 Correct 739 ms 4388 KB Output is correct
23 Correct 3575 ms 8464 KB Output is correct
24 Correct 3968 ms 8568 KB Output is correct
25 Correct 2888 ms 8452 KB Output is correct
26 Correct 3881 ms 8568 KB Output is correct
27 Correct 3976 ms 8456 KB Output is correct
28 Correct 1741 ms 2808 KB Output is correct
29 Correct 1658 ms 2808 KB Output is correct
30 Correct 1721 ms 2728 KB Output is correct
31 Correct 1645 ms 2808 KB Output is correct
32 Correct 3361 ms 8544 KB Output is correct
33 Correct 2813 ms 8568 KB Output is correct
34 Correct 2948 ms 8452 KB Output is correct
35 Correct 2940 ms 8452 KB Output is correct
36 Correct 3299 ms 8456 KB Output is correct
37 Correct 3981 ms 8636 KB Output is correct
38 Correct 3037 ms 8568 KB Output is correct
39 Correct 2988 ms 8568 KB Output is correct
40 Correct 3300 ms 8440 KB Output is correct
41 Correct 4930 ms 8440 KB Output is correct
42 Correct 5025 ms 8452 KB Output is correct