oj.uz

Submission #498849

# Submission time Handle Problem Language Result Execution time Memory
498849 2021-12-26T12:57:28 Z sidon Dancing Elephants (IOI11_elephants) C++17
50 / 100
 1466 ms 4928 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], p = inB[i];
	a[l].erase(begin(a[l]) + p);
	recalculate(l);
 
	s.erase (make_pair(X[i], i));
	X[i] = y;
 
 	l = Y[(*--s.upper_bound(make_pair(X[i], N))).second];
	
	s.insert(make_pair(X[i], i));

 	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 1 ms 332 KB Output is correct
2 Correct 0 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 0 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 332 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 0 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 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 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 0 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 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 KB Output is correct
14 Runtime error 194 ms 4776 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 0 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 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 KB Output is correct
14 Runtime error 194 ms 4776 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -