oj.uz

Submission #498841

# Submission time Handle Problem Language Result Execution time Memory
498841 2021-12-26T12:48:41 Z sidon Dancing Elephants (IOI11_elephants) C++17
26 / 100
 945 ms 4664 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], Y[MAX_N], num[MAX_N], pos[MAX_N], inB[MAX_N], q_;
 
vector<int> a[B];
set<pair<int, int>> s;
 
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;
		inB[c[i]] = i;
	}
}
 
void reset() {
	for(int i = 0, j = 0; i < LIM; i++) {
		for(int &v : a[i]) pos[j++] = v;
		a[i].clear();
	}
	for(int i = 0; i < N; i++) {
		Y[pos[i]] = i/B;
		a[i/B].push_back(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);
		s.insert({X[i], i});
	}
	reset();
}

int update(int i, int y) {
	int l = Y[i];
	int p = inB[i];
	a[l].erase(begin(a[l]) + p);
	recalculate(l);
 
	s.erase (make_pair(X[i], i));
	X[i] = y;
	s.insert(make_pair(X[i], i));
 
 	l = Y[(*--s.upper_bound(make_pair(X[i], N))).second];
 	for(p = 0; p < (int)size(a[l]); ++p)
 		if(X[i] <= X[a[l][p]]) break;
	Y[i] = l;
	a[l].insert(begin(a[l]) + p, i);
	recalculate(l);
 
	if(!(++q_ % (B - 2))) reset();
 
	int res = 0, curr = -1;
 
	for(int k = 0; k < LIM; k++) {
		if(empty(a[k]) || curr >= X[a[k].back()]) continue;

 		int j = inB[(*s.upper_bound(make_pair(curr, N))).second];
 
		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 0 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 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

Subtask #3
0 / 24.0

# 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 811 ms 1868 KB Output is correct
8 Correct 842 ms 2252 KB Output is correct
9 Correct 945 ms 4664 KB Output is correct
10 Incorrect 28 ms 4548 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 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 811 ms 1868 KB Output is correct
8 Correct 842 ms 2252 KB Output is correct
9 Correct 945 ms 4664 KB Output is correct
10 Incorrect 28 ms 4548 KB Output isn't correct
11 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 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 811 ms 1868 KB Output is correct
8 Correct 842 ms 2252 KB Output is correct
9 Correct 945 ms 4664 KB Output is correct
10 Incorrect 28 ms 4548 KB Output isn't correct
11 Halted 0 ms 0 KB -