oj.uz

Submission #207732

# Submission time Handle Problem Language Result Execution time Memory
207732 2020-03-08T17:26:17 Z cgiosy Dancing Elephants (IOI11_elephants) C++17
100 / 100
 3921 ms 7800 KB 
#include <bits/stdc++.h>
#define lb(a, x) lower_bound(begin(a), end(a), x)
using namespace std;
constexpr int MX=150000, B=384, 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 1912 KB Output is correct
2 Correct 5 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 5 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1912 KB Output is correct
7 Correct 385 ms 2992 KB Output is correct
8 Correct 404 ms 3064 KB Output is correct
9 Correct 401 ms 3576 KB Output is correct
10 Correct 381 ms 3320 KB Output is correct
11 Correct 351 ms 3384 KB Output is correct
12 Correct 655 ms 3980 KB Output is correct
13 Correct 395 ms 3448 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 5 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1912 KB Output is correct
7 Correct 385 ms 2992 KB Output is correct
8 Correct 404 ms 3064 KB Output is correct
9 Correct 401 ms 3576 KB Output is correct
10 Correct 381 ms 3320 KB Output is correct
11 Correct 351 ms 3384 KB Output is correct
12 Correct 655 ms 3980 KB Output is correct
13 Correct 395 ms 3448 KB Output is correct
14 Correct 404 ms 3320 KB Output is correct
15 Correct 606 ms 3576 KB Output is correct
16 Correct 1082 ms 4228 KB Output is correct
17 Correct 1125 ms 4856 KB Output is correct
18 Correct 1220 ms 4728 KB Output is correct
19 Correct 620 ms 3960 KB Output is correct
20 Correct 1115 ms 4728 KB Output is correct
21 Correct 1088 ms 4856 KB Output is correct
22 Correct 673 ms 3832 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1912 KB Output is correct
2 Correct 5 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1912 KB Output is correct
7 Correct 385 ms 2992 KB Output is correct
8 Correct 404 ms 3064 KB Output is correct
9 Correct 401 ms 3576 KB Output is correct
10 Correct 381 ms 3320 KB Output is correct
11 Correct 351 ms 3384 KB Output is correct
12 Correct 655 ms 3980 KB Output is correct
13 Correct 395 ms 3448 KB Output is correct
14 Correct 404 ms 3320 KB Output is correct
15 Correct 606 ms 3576 KB Output is correct
16 Correct 1082 ms 4228 KB Output is correct
17 Correct 1125 ms 4856 KB Output is correct
18 Correct 1220 ms 4728 KB Output is correct
19 Correct 620 ms 3960 KB Output is correct
20 Correct 1115 ms 4728 KB Output is correct
21 Correct 1088 ms 4856 KB Output is correct
22 Correct 673 ms 3832 KB Output is correct
23 Correct 3033 ms 7088 KB Output is correct
24 Correct 3352 ms 7560 KB Output is correct
25 Correct 2350 ms 6820 KB Output is correct
26 Correct 2930 ms 5760 KB Output is correct
27 Correct 2828 ms 5764 KB Output is correct
28 Correct 1357 ms 3960 KB Output is correct
29 Correct 1282 ms 3960 KB Output is correct
30 Correct 1324 ms 3960 KB Output is correct
31 Correct 1286 ms 3832 KB Output is correct
32 Correct 2230 ms 5752 KB Output is correct
33 Correct 1890 ms 5880 KB Output is correct
34 Correct 2444 ms 5800 KB Output is correct
35 Correct 1932 ms 7620 KB Output is correct
36 Correct 1589 ms 5756 KB Output is correct
37 Correct 3005 ms 7672 KB Output is correct
38 Correct 2529 ms 5752 KB Output is correct
39 Correct 2201 ms 5752 KB Output is correct
40 Correct 2767 ms 5752 KB Output is correct
41 Correct 3796 ms 7800 KB Output is correct
42 Correct 3921 ms 7592 KB Output is correct