oj.uz

Submission #498705

# Submission time Handle Problem Language Result Execution time Memory
498705 2021-12-26T08:15:56 Z sidon Dancing Elephants (IOI11_elephants) C++17
50 / 100
 846 ms 4636 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];
	if(empty(c)) return;
 
	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 = 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)) 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 590 ms 2244 KB Output is correct
8 Correct 636 ms 2356 KB Output is correct
9 Correct 483 ms 3680 KB Output is correct
10 Correct 495 ms 3556 KB Output is correct
11 Correct 461 ms 3400 KB Output is correct
12 Correct 846 ms 3708 KB Output is correct
13 Correct 562 ms 3260 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 590 ms 2244 KB Output is correct
8 Correct 636 ms 2356 KB Output is correct
9 Correct 483 ms 3680 KB Output is correct
10 Correct 495 ms 3556 KB Output is correct
11 Correct 461 ms 3400 KB Output is correct
12 Correct 846 ms 3708 KB Output is correct
13 Correct 562 ms 3260 KB Output is correct
14 Runtime error 214 ms 4636 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 590 ms 2244 KB Output is correct
8 Correct 636 ms 2356 KB Output is correct
9 Correct 483 ms 3680 KB Output is correct
10 Correct 495 ms 3556 KB Output is correct
11 Correct 461 ms 3400 KB Output is correct
12 Correct 846 ms 3708 KB Output is correct
13 Correct 562 ms 3260 KB Output is correct
14 Runtime error 214 ms 4636 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -