oj.uz

Submission #498629

# Submission time Handle Problem Language Result Execution time Memory
498629 2021-12-25T21:10:42 Z sidon Dancing Elephants (IOI11_elephants) C++17
26 / 100
 467 ms 3780 KB 
#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
 
const int MAX_N = 150'000, B = 400, NB = 500, INF = 2e9;
 
int N, L, X[MAX_N], num[MAX_N], pos[MAX_N], st[NB];
 
vector<int> a[NB], b[NB];
 
void recalculate(int j) {
	auto &c = a[j];
 
	st[j] = INF;
	if(empty(c)) return;
	st[j] = b[j][0];
 
	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() {
	int pt = 0;
 
	for(auto &c : a) {
		for(int &i : c) pos[pt++] = i;
		c.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 < NB; i++)
		recalculate(i);
}
 
void init(int n, int l, int x[]) {
	N = n, L = l;
	for(int i = 0; i < N; i++) {
		X[i] = x[i];
		a[i/B].push_back(i);
	}
 
	reset();
}
 
int l, p;
 
void locate(int i){
	l = upper_bound(st, st+NB, X[i]) - st - 1;
    if(l < 0) l = 0;
	p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
}
 
int update(int i, int y) {
	int redo = 0;
 
	locate(i);
	a[l].erase(begin(a[l]) + p);
	b[l].erase(begin(b[l]) + p);
 
	recalculate(l);
 
	if(empty(b[l]) || size(b[l]) == NB*2)
		redo = 1;
 
	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(redo || empty(b[l]) || size(b[l]) == NB*2)
		reset();
 
	int res = 0, cur = -1;
 
	for(int k = 0; k < NB; k++) {
		if(st[k] == INF) break;
		if(cur >= b[k].back()) continue;
 
		int j = upper_bound(begin(b[k]), end(b[k]), cur) - begin(b[k]);
 
		res += num[a[k][j]];
		cur = 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 324 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 324 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 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 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 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 459 ms 2164 KB Output is correct
8 Correct 467 ms 2396 KB Output is correct
9 Correct 376 ms 3780 KB Output is correct
10 Incorrect 25 ms 3780 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 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 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 459 ms 2164 KB Output is correct
8 Correct 467 ms 2396 KB Output is correct
9 Correct 376 ms 3780 KB Output is correct
10 Incorrect 25 ms 3780 KB Output isn't correct
11 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 324 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 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 459 ms 2164 KB Output is correct
8 Correct 467 ms 2396 KB Output is correct
9 Correct 376 ms 3780 KB Output is correct
10 Incorrect 25 ms 3780 KB Output isn't correct
11 Halted 0 ms 0 KB -