oj.uz

답안 #233927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233927 2020-05-22T12:31:02 Z crossing0ver 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 4920 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int K = 400, MXN = 1.5E5 + 5;
const int B = MXN/K + 9;
int P[150000], inbox[150000] , L, n; 
struct BLOCK{
	int sz;
	int arr[K*1000 + 10] , last[K*1000 + 10], cost[K*1000 + 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() {
	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(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+= 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct
7 Execution timed out 9057 ms 4920 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct
7 Execution timed out 9057 ms 4920 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 6 ms 3456 KB Output is correct
7 Execution timed out 9057 ms 4920 KB Time limit exceeded
8 Halted 0 ms 0 KB -