Submission #498752

# Submission time Handle Problem Language Result Execution time Memory
498752 2021-12-26T09:59:47 Z sidon Dancing Elephants (IOI11_elephants) C++17
50 / 100
793 ms 3052 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();
		if(i + 1 == LIM)
			assert(j == N);
	}
	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(l = 0; l < LIM; l++)
		if(!empty(b[l]) && b[l][0] > X[i]) break;
	if(l) --l;
	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;
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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 554 ms 1348 KB Output is correct
8 Correct 606 ms 1356 KB Output is correct
9 Correct 487 ms 2168 KB Output is correct
10 Correct 472 ms 2132 KB Output is correct
11 Correct 481 ms 2128 KB Output is correct
12 Correct 793 ms 2452 KB Output is correct
13 Correct 476 ms 2128 KB Output is correct
# Verdict Execution time Memory 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 554 ms 1348 KB Output is correct
8 Correct 606 ms 1356 KB Output is correct
9 Correct 487 ms 2168 KB Output is correct
10 Correct 472 ms 2132 KB Output is correct
11 Correct 481 ms 2128 KB Output is correct
12 Correct 793 ms 2452 KB Output is correct
13 Correct 476 ms 2128 KB Output is correct
14 Runtime error 196 ms 3052 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory 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 554 ms 1348 KB Output is correct
8 Correct 606 ms 1356 KB Output is correct
9 Correct 487 ms 2168 KB Output is correct
10 Correct 472 ms 2132 KB Output is correct
11 Correct 481 ms 2128 KB Output is correct
12 Correct 793 ms 2452 KB Output is correct
13 Correct 476 ms 2128 KB Output is correct
14 Runtime error 196 ms 3052 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -