oj.uz

Submission #498706

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -