oj.uz

답안 #498706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498706 2021-12-26T08:36:27 Z sidon 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 781 ms 3092 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 ; ) {
		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++) {
		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]);
 
		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 1 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 1 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 0 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 1 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 0 ms 332 KB Output is correct
7 Correct 582 ms 1228 KB Output is correct
8 Correct 611 ms 1356 KB Output is correct
9 Correct 499 ms 2244 KB Output is correct
10 Correct 502 ms 2124 KB Output is correct
11 Correct 468 ms 2128 KB Output is correct
12 Correct 781 ms 2448 KB Output is correct
13 Correct 500 ms 2132 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 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 0 ms 332 KB Output is correct
7 Correct 582 ms 1228 KB Output is correct
8 Correct 611 ms 1356 KB Output is correct
9 Correct 499 ms 2244 KB Output is correct
10 Correct 502 ms 2124 KB Output is correct
11 Correct 468 ms 2128 KB Output is correct
12 Correct 781 ms 2448 KB Output is correct
13 Correct 500 ms 2132 KB Output is correct
14 Runtime error 200 ms 3092 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 1 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 0 ms 332 KB Output is correct
7 Correct 582 ms 1228 KB Output is correct
8 Correct 611 ms 1356 KB Output is correct
9 Correct 499 ms 2244 KB Output is correct
10 Correct 502 ms 2124 KB Output is correct
11 Correct 468 ms 2128 KB Output is correct
12 Correct 781 ms 2448 KB Output is correct
13 Correct 500 ms 2132 KB Output is correct
14 Runtime error 200 ms 3092 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -