oj.uz

Submission #207730

# Submission time Handle Problem Language Result Execution time Memory
207730 2020-03-08T17:20:59 Z cgiosy Dancing Elephants (IOI11_elephants) C++17
26 / 100
 25 ms 3192 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 i=v.size(), 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 6 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 5 ms 1528 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 5 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
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 5 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 Incorrect 25 ms 3192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 5 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 Incorrect 25 ms 3192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 5 ms 1528 KB Output is correct
3 Correct 5 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 Incorrect 25 ms 3192 KB Output isn't correct
8 Halted 0 ms 0 KB -