oj.uz

Submission #62194

# Submission time Handle Problem Language Result Execution time Memory
62194 2018-07-27T19:18:46 Z reality Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 85212 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;

int K;

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;
	K = sqrt(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:126: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 67 ms 70776 KB Output is correct
2 Correct 75 ms 70904 KB Output is correct
3 Correct 73 ms 70904 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 75 ms 70904 KB Output is correct
3 Correct 73 ms 70904 KB Output is correct
4 Correct 68 ms 71088 KB Output is correct
5 Correct 74 ms 71088 KB Output is correct
6 Correct 73 ms 71088 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 75 ms 70904 KB Output is correct
3 Correct 73 ms 70904 KB Output is correct
4 Correct 68 ms 71088 KB Output is correct
5 Correct 74 ms 71088 KB Output is correct
6 Correct 73 ms 71088 KB Output is correct
7 Correct 536 ms 72716 KB Output is correct
8 Correct 652 ms 73172 KB Output is correct
9 Correct 1004 ms 75440 KB Output is correct
10 Correct 831 ms 75440 KB Output is correct
11 Correct 991 ms 75440 KB Output is correct
12 Correct 1421 ms 75652 KB Output is correct
13 Correct 849 ms 75652 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 75 ms 70904 KB Output is correct
3 Correct 73 ms 70904 KB Output is correct
4 Correct 68 ms 71088 KB Output is correct
5 Correct 74 ms 71088 KB Output is correct
6 Correct 73 ms 71088 KB Output is correct
7 Correct 536 ms 72716 KB Output is correct
8 Correct 652 ms 73172 KB Output is correct
9 Correct 1004 ms 75440 KB Output is correct
10 Correct 831 ms 75440 KB Output is correct
11 Correct 991 ms 75440 KB Output is correct
12 Correct 1421 ms 75652 KB Output is correct
13 Correct 849 ms 75652 KB Output is correct
14 Correct 956 ms 75652 KB Output is correct
15 Correct 1173 ms 75652 KB Output is correct
16 Correct 2706 ms 75844 KB Output is correct
17 Correct 2906 ms 77644 KB Output is correct
18 Correct 3468 ms 77644 KB Output is correct
19 Correct 1801 ms 77644 KB Output is correct
20 Correct 3239 ms 77644 KB Output is correct
21 Correct 3192 ms 77644 KB Output is correct
22 Correct 1638 ms 77644 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 75 ms 70904 KB Output is correct
3 Correct 73 ms 70904 KB Output is correct
4 Correct 68 ms 71088 KB Output is correct
5 Correct 74 ms 71088 KB Output is correct
6 Correct 73 ms 71088 KB Output is correct
7 Correct 536 ms 72716 KB Output is correct
8 Correct 652 ms 73172 KB Output is correct
9 Correct 1004 ms 75440 KB Output is correct
10 Correct 831 ms 75440 KB Output is correct
11 Correct 991 ms 75440 KB Output is correct
12 Correct 1421 ms 75652 KB Output is correct
13 Correct 849 ms 75652 KB Output is correct
14 Correct 956 ms 75652 KB Output is correct
15 Correct 1173 ms 75652 KB Output is correct
16 Correct 2706 ms 75844 KB Output is correct
17 Correct 2906 ms 77644 KB Output is correct
18 Correct 3468 ms 77644 KB Output is correct
19 Correct 1801 ms 77644 KB Output is correct
20 Correct 3239 ms 77644 KB Output is correct
21 Correct 3192 ms 77644 KB Output is correct
22 Correct 1638 ms 77644 KB Output is correct
23 Correct 5875 ms 83856 KB Output is correct
24 Correct 6500 ms 84072 KB Output is correct
25 Correct 5782 ms 84072 KB Output is correct
26 Correct 6170 ms 84072 KB Output is correct
27 Correct 6130 ms 84072 KB Output is correct
28 Correct 1071 ms 84072 KB Output is correct
29 Correct 1040 ms 84072 KB Output is correct
30 Correct 1268 ms 84072 KB Output is correct
31 Correct 1316 ms 84072 KB Output is correct
32 Correct 5880 ms 84072 KB Output is correct
33 Correct 5334 ms 84072 KB Output is correct
34 Correct 5331 ms 84072 KB Output is correct
35 Correct 5794 ms 85212 KB Output is correct
36 Correct 4530 ms 85212 KB Output is correct
37 Execution timed out 9059 ms 85212 KB Time limit exceeded
38 Halted 0 ms 0 KB -