oj.uz

Submission #207731

# Submission time Handle Problem Language Result Execution time Memory
207731 2020-03-08T17:24:12 Z cgiosy Dancing Elephants (IOI11_elephants) C++17
100 / 100
 3795 ms 12460 KB 
#include <bits/stdc++.h>
#define lb(a, x) lower_bound(begin(a), end(a), x)
using namespace std;
constexpr int MX=150000, B=512, C=(MX+B-1)/B;

struct iii { int x, n, y; };
bool operator<(const iii& a, int b) { return a.x<b; }
bool operator<(int a, const iii& b) { return a<b.x; }
int A[MX], X[MX], N, M, Q;
vector<iii> D[C];
void calc_bucket(vector<iii>& v) {
	for(int n=v.size(), i=n, p=n; i--;) {
		while(p && v[i].x<v[p-1].x-M) p--;
		if(p==n) v[i].n=1, v[i].y=v[i].x+M;
		else v[i].n=v[p].n+1, v[i].y=v[p].y;
	}
}
void init_buckets() {
	int k=0;
	for(auto&v:D) {
		for(auto[x,n,y]:v) X[k++]=x;
		v.clear();
	}
	for(int i=0, j=0; i<N;) {
		D[j].push_back({X[i], 0, 0});
		if(++i%B==0 || i==N) calc_bucket(D[j++]);
	}
}
void del(int x) {
	for(auto&v:D) if(v.size() && v.front().x<=x && x<=v.back().x) {
		v.erase(lb(v, x));
		calc_bucket(v);
		break;
	}
}
void add(int x) {
	int p=0, n=N-1;
	for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
		v.insert(lb(v, x), {x, 0, 0});
		calc_bucket(v);
		break;
	}
}
int answer() {
	int p=0, n=0;
	for(auto&v:D) if(v.size() && p<=v.back().x) {
		auto[x,m,y]=*lb(v, p);
		n+=m, p=y+1;
	}
	return n;
}

void init(int n, int m, int E[]) {
	N=n, M=m;
	for(int i=0; i<C; i++) D[i].reserve(B);
	for(int i=0; i<N; i++) D[i/B].push_back({A[i]=E[i], 0, 0});
}
int update(int n, int x) {
	if(Q++%B==0) init_buckets();
	del(A[n]);
	add(A[n]=x);
	return answer();
}

Compilation message

elephants.cpp: In function 'void init_buckets()':
elephants.cpp:21:17: warning: unused variable 'n' [-Wunused-variable]
   for(auto[x,n,y]:v) X[k++]=x;
                 ^
elephants.cpp:21:17: warning: unused variable 'y' [-Wunused-variable]
elephants.cpp: In function 'void add(int)':
elephants.cpp:38:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
                                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int answer()':
elephants.cpp:47:13: warning: unused variable 'x' [-Wunused-variable]
   auto[x,m,y]=*lb(v, p);
             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 6 ms 1528 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 6 ms 1528 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 470 ms 2552 KB Output is correct
8 Correct 493 ms 3672 KB Output is correct
9 Correct 433 ms 4732 KB Output is correct
10 Correct 403 ms 4216 KB Output is correct
11 Correct 413 ms 4344 KB Output is correct
12 Correct 701 ms 4984 KB Output is correct
13 Correct 404 ms 4088 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 6 ms 1528 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 470 ms 2552 KB Output is correct
8 Correct 493 ms 3672 KB Output is correct
9 Correct 433 ms 4732 KB Output is correct
10 Correct 403 ms 4216 KB Output is correct
11 Correct 413 ms 4344 KB Output is correct
12 Correct 701 ms 4984 KB Output is correct
13 Correct 404 ms 4088 KB Output is correct
14 Correct 479 ms 4348 KB Output is correct
15 Correct 746 ms 4344 KB Output is correct
16 Correct 1222 ms 5496 KB Output is correct
17 Correct 1223 ms 6392 KB Output is correct
18 Correct 1283 ms 6264 KB Output is correct
19 Correct 586 ms 5752 KB Output is correct
20 Correct 1191 ms 6264 KB Output is correct
21 Correct 1117 ms 6008 KB Output is correct
22 Correct 674 ms 5112 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 6 ms 1528 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 470 ms 2552 KB Output is correct
8 Correct 493 ms 3672 KB Output is correct
9 Correct 433 ms 4732 KB Output is correct
10 Correct 403 ms 4216 KB Output is correct
11 Correct 413 ms 4344 KB Output is correct
12 Correct 701 ms 4984 KB Output is correct
13 Correct 404 ms 4088 KB Output is correct
14 Correct 479 ms 4348 KB Output is correct
15 Correct 746 ms 4344 KB Output is correct
16 Correct 1222 ms 5496 KB Output is correct
17 Correct 1223 ms 6392 KB Output is correct
18 Correct 1283 ms 6264 KB Output is correct
19 Correct 586 ms 5752 KB Output is correct
20 Correct 1191 ms 6264 KB Output is correct
21 Correct 1117 ms 6008 KB Output is correct
22 Correct 674 ms 5112 KB Output is correct
23 Correct 2905 ms 11964 KB Output is correct
24 Correct 3136 ms 11896 KB Output is correct
25 Correct 2098 ms 11568 KB Output is correct
26 Correct 2691 ms 10744 KB Output is correct
27 Correct 2553 ms 10584 KB Output is correct
28 Correct 1674 ms 6408 KB Output is correct
29 Correct 1604 ms 6416 KB Output is correct
30 Correct 1651 ms 6392 KB Output is correct
31 Correct 1612 ms 6520 KB Output is correct
32 Correct 2247 ms 10284 KB Output is correct
33 Correct 1837 ms 9592 KB Output is correct
34 Correct 2233 ms 10468 KB Output is correct
35 Correct 1820 ms 12428 KB Output is correct
36 Correct 1592 ms 10140 KB Output is correct
37 Correct 2826 ms 12460 KB Output is correct
38 Correct 2336 ms 9380 KB Output is correct
39 Correct 1921 ms 10488 KB Output is correct
40 Correct 2556 ms 9640 KB Output is correct
41 Correct 3707 ms 12028 KB Output is correct
42 Correct 3795 ms 12160 KB Output is correct