oj.uz

Submission #62196

# Submission time Handle Problem Language Result Execution time Memory
62196 2018-07-27T19:29:52 Z reality Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 83672 KB 
#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

int n,l;
vi s;

const int K = 2000;

const int oo = 2e9 + 5;

const int NN = 1e6 + 5;

int Step = 0;

multiset < int > ss;

vi v[NN];

vi dp1[NN];

vi dp2[NN];

int SZ;

void build_block(int w) {
	int sz = v[w].size();
	int index = sz;
	dp1[w].resize(sz);
	dp2[w].resize(sz);
	for (int j = sz - 1;j >= 0;--j) {
		while (v[w][j] + l < v[w][index - 1])
			--index;
		dp1[w][j] = 1;
		dp2[w][j] = v[w][j];
		if (index < sz)
			dp1[w][j] += dp1[w][index],dp2[w][j] = dp2[w][index];
	}
}

void del(int val) {
	for (int i = 0;i < SZ;++i) 
		if (!v[i].empty() && v[i][0] <= val && val <= v[i].back()) {
			vi nw;
			for (auto it : v[i])
				if (it != val)
					nw.pb(it);
				else
					val = oo;
			assert(nw.size() + 1 == v[i].size());
			v[i] = nw;
			build_block(i);
			break;
		}
}

void add(int val) {
	int pr = SZ - 1;
	for (int i = 0;i < SZ;++i) 
		if (!v[i].empty() && val <= v[i].back()) {
			pr = i;
			break;
		}
	vi nw;
	for (auto it : v[pr]) {
		if (it > val)
			nw.pb(val),val = oo;
		nw.pb(it);
	}
	if (val != oo)
		nw.pb(val);
	v[pr] = nw;
	build_block(pr);
}

void build(void) {
	int index = -1;
	SZ = (ss.size() + K - 1) / K;
	for (int i = 0;i < SZ;++i)
		v[i].clear(),dp1[i].clear(),dp2[i].clear();
	for (auto it : ss) {
		++index;
		v[index / K].pb(it);
	}
	for (int i = 0;i < SZ;++i) {
		build_block(i);
	}
}

void init(int N, int L, int X[]) {
	n = N;
	l = L;
	for (int i = 0;i < n;++i)
		s.pb(X[i]),ss.insert(X[i]);
}

int update(int i, int y) {
	if (!(Step % K)) {
		build();
	}
	++Step;
	ss.erase(ss.find(s[i]));
	del(s[i]);
	ss.insert(y);
	add(s[i] = y);
	int prev = -oo;
	int ans = 0;
	for (int i = 0;i < SZ;++i) {
		if (v[i].empty())
			continue;
		int low = lower_bound(all(v[i]),prev) - v[i].begin();
		if (low != v[i].size()) {
			ans += dp1[i][low];
			prev = dp2[i][low] + l + 1;
		}
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:125:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (low != v[i].size()) {
       ~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 70776 KB Output is correct
2 Correct 67 ms 70836 KB Output is correct
3 Correct 70 ms 70836 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 70776 KB Output is correct
2 Correct 67 ms 70836 KB Output is correct
3 Correct 70 ms 70836 KB Output is correct
4 Correct 61 ms 70996 KB Output is correct
5 Correct 68 ms 70996 KB Output is correct
6 Correct 65 ms 70996 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 70776 KB Output is correct
2 Correct 67 ms 70836 KB Output is correct
3 Correct 70 ms 70836 KB Output is correct
4 Correct 61 ms 70996 KB Output is correct
5 Correct 68 ms 70996 KB Output is correct
6 Correct 65 ms 70996 KB Output is correct
7 Correct 1868 ms 72876 KB Output is correct
8 Correct 1826 ms 73244 KB Output is correct
9 Correct 2165 ms 75312 KB Output is correct
10 Correct 2056 ms 75312 KB Output is correct
11 Correct 1995 ms 75312 KB Output is correct
12 Correct 3142 ms 75524 KB Output is correct
13 Correct 2260 ms 75524 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 70776 KB Output is correct
2 Correct 67 ms 70836 KB Output is correct
3 Correct 70 ms 70836 KB Output is correct
4 Correct 61 ms 70996 KB Output is correct
5 Correct 68 ms 70996 KB Output is correct
6 Correct 65 ms 70996 KB Output is correct
7 Correct 1868 ms 72876 KB Output is correct
8 Correct 1826 ms 73244 KB Output is correct
9 Correct 2165 ms 75312 KB Output is correct
10 Correct 2056 ms 75312 KB Output is correct
11 Correct 1995 ms 75312 KB Output is correct
12 Correct 3142 ms 75524 KB Output is correct
13 Correct 2260 ms 75524 KB Output is correct
14 Correct 2721 ms 75524 KB Output is correct
15 Correct 3005 ms 75524 KB Output is correct
16 Correct 5257 ms 75524 KB Output is correct
17 Correct 5186 ms 77108 KB Output is correct
18 Correct 5175 ms 77312 KB Output is correct
19 Correct 2685 ms 77312 KB Output is correct
20 Correct 4478 ms 77312 KB Output is correct
21 Correct 4661 ms 77312 KB Output is correct
22 Correct 2726 ms 77312 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 70776 KB Output is correct
2 Correct 67 ms 70836 KB Output is correct
3 Correct 70 ms 70836 KB Output is correct
4 Correct 61 ms 70996 KB Output is correct
5 Correct 68 ms 70996 KB Output is correct
6 Correct 65 ms 70996 KB Output is correct
7 Correct 1868 ms 72876 KB Output is correct
8 Correct 1826 ms 73244 KB Output is correct
9 Correct 2165 ms 75312 KB Output is correct
10 Correct 2056 ms 75312 KB Output is correct
11 Correct 1995 ms 75312 KB Output is correct
12 Correct 3142 ms 75524 KB Output is correct
13 Correct 2260 ms 75524 KB Output is correct
14 Correct 2721 ms 75524 KB Output is correct
15 Correct 3005 ms 75524 KB Output is correct
16 Correct 5257 ms 75524 KB Output is correct
17 Correct 5186 ms 77108 KB Output is correct
18 Correct 5175 ms 77312 KB Output is correct
19 Correct 2685 ms 77312 KB Output is correct
20 Correct 4478 ms 77312 KB Output is correct
21 Correct 4661 ms 77312 KB Output is correct
22 Correct 2726 ms 77312 KB Output is correct
23 Correct 7841 ms 83448 KB Output is correct
24 Correct 8829 ms 83672 KB Output is correct
25 Correct 6300 ms 83672 KB Output is correct
26 Correct 7915 ms 83672 KB Output is correct
27 Correct 8213 ms 83672 KB Output is correct
28 Correct 8542 ms 83672 KB Output is correct
29 Execution timed out 9076 ms 83672 KB Time limit exceeded
30 Halted 0 ms 0 KB -