oj.uz

답안 #498746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498746 2021-12-26T09:39:30 Z sidon 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 830 ms 3212 KB 
#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
 
const int MAX_N = 150'000, B = 500, INF = 2e9;
 
int N, L, LIM, X[MAX_N], num[MAX_N], pos[MAX_N];
 
vector<int> a[B], b[B];
 
void recalculate(int j) {
	auto &c = a[j];
	int sz = size(c), pt = sz;
 
	for(int i = sz; --i >= 0; ) {
		assert(0 <= c[i] && c[i] < N);
		while(pt && X[c[i]] + L < X[c[pt-1]]) --pt;
 
		num[c[i]] = pt < sz ? num[c[pt]] + 1 : 1;
		pos[c[i]] = pt < sz ? pos[c[pt]] : X[c[i]] + L;
	}
}
 
void reset() {
	for(int i = 0, j = 0; i < LIM; i++) {
		for(int &v : a[i]) pos[j++] = v;
		a[i].clear();
		b[i].clear();
	}
	for(int i = 0; i < N; i++) {
		assert(0 <= pos[i] && pos[i] < N);
		a[i/B].push_back(pos[i]);
		b[i/B].push_back(X[pos[i]]);
	}
	for(int i = 0; i < LIM; i++)
		recalculate(i);
}
 
void init(int n, int l, int x[]) {
	N = n, L = l, LIM = (N - 1)/B + 1;
	for(int i = 0; i < N; i++) {
		X[i] = x[i];
		a[i/B].push_back(i);
	}
	reset();
}
 
int l, p, q_;
 
void locate(int i){
	for(int j = l = 0; j < LIM; j++)
		if(!empty(b[j]) && b[j][0] <= X[i]) l = j;
	p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
}
 
int update(int i, int y) {
	locate(i);
	while(a[l][p] != i) ++p;
	a[l].erase(begin(a[l]) + p);
	b[l].erase(begin(b[l]) + p);
	recalculate(l);
 
	X[i] = y;
 
	locate(i);
	a[l].insert(begin(a[l]) + p, i);
	b[l].insert(begin(b[l]) + p, X[i]);
	recalculate(l);
 
	if(!(++q_ % (B - 2))) reset();
 
	int res = 0, curr = -1;
 
	for(int k = 0; k < LIM; k++) {
		if(empty(b[k]) || curr >= b[k].back()) continue;
 
		int j = upper_bound(begin(b[k]), end(b[k]), curr) - begin(b[k]);

		assert(0 <= a[k][j] && a[k][j] <= N);
 
		res += num[a[k][j]];
		curr = pos[a[k][j]];
	}
	return res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 619 ms 1228 KB Output is correct
8 Correct 612 ms 1476 KB Output is correct
9 Correct 473 ms 2128 KB Output is correct
10 Correct 481 ms 2128 KB Output is correct
11 Correct 501 ms 2132 KB Output is correct
12 Correct 830 ms 2316 KB Output is correct
13 Correct 490 ms 2132 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 619 ms 1228 KB Output is correct
8 Correct 612 ms 1476 KB Output is correct
9 Correct 473 ms 2128 KB Output is correct
10 Correct 481 ms 2128 KB Output is correct
11 Correct 501 ms 2132 KB Output is correct
12 Correct 830 ms 2316 KB Output is correct
13 Correct 490 ms 2132 KB Output is correct
14 Runtime error 190 ms 3212 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 619 ms 1228 KB Output is correct
8 Correct 612 ms 1476 KB Output is correct
9 Correct 473 ms 2128 KB Output is correct
10 Correct 481 ms 2128 KB Output is correct
11 Correct 501 ms 2132 KB Output is correct
12 Correct 830 ms 2316 KB Output is correct
13 Correct 490 ms 2132 KB Output is correct
14 Runtime error 190 ms 3212 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -