Submission #874321

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
874321	2023-11-16T16:35:36 Z	phoenix0423	Lightning Conductor (POI11_pio)	C++17	100 / 100	253 ms	21888 KB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int N = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e4 + 5;

struct info{
	int l, r, id;
	info(){}
	info(int _l, int _r, int _id) : l(_l), r(_r), id(_id){}
};
const double eps = 1e-9;

ll rd(double d){
	if(d - ll(d) < eps) return ll(d);
	else return ll(d) + 1;
}
int main(void){
	fastio;
	int n;
	cin>>n;
	vector<int> h(n);
	for(int i = 0; i < n; i++) cin>>h[i];
	vector<int> d(n);
	d[0] = 0;
	int cur = 0;
	for(int i = 1; i < n; i++){
		d[i] = d[i - 1];
		if(cur * cur == i - 1) d[i] ++, cur++;
	}
	auto f = [&](int id, int j) -> double{
		if(id == j) return h[id];
		return h[id] + sqrt(abs(id - j));
	};
	vector<ll> dpl(n), dpr(n);
	deque<info> dq;
	dq.pb(info(1, n - 1, 0));
	for(int i = 1; i < n; i++){
		while(dq.front().r < i) dq.pop_front();
		dpl[i] = rd(f(dq.front().id, i));
		dq.front().l++;
		while(dq.size()){
			auto [l, r, id] = dq.back();
			if(f(id, max(l, i + 1)) < f(i, max(l, i + 1))) dq.pop_back();
			else break;
		}
		if(!dq.size()){
			dq.pb(info(i + 1, n - 1, i));
			continue;
		}
		int l = max(dq.back().l, i + 1), r = n;
		while(l + 1 < r){
			int m = (l + r) / 2;
			auto [l2, r2, id] = dq.back();
			if(f(id, m) < f(i, m)) r = m;
			else l = m;
		}
		dq.back().r = r - 1;
		if(r < n) dq.pb(info(r, n - 1, i));
	}
	dq.clear();
	dq.pb(info(0, n - 2, n - 1));
	for(int i = n - 2; i >= 0; i--){
		while(dq.front().l > i) dq.pop_front();
		dq.front().r--;
		dpr[i] = rd(f(dq.front().id, i));
		while(dq.size()){	
			auto [l, r, id] = dq.back();
			if(f(id, min(i - 1, r)) < f(i, min(i - 1, r))) dq.pop_back();
			else break;
		}
		if(!dq.size()){
			dq.pb(info(0, i - 1, i));
			continue;
		}
		int l = -1, r = min(dq.back().r, i - 1);
		while(l + 1 < r){
			int m = (l + r) / 2;
			auto [l2, r2, id] = dq.back();
			if(f(id, m) < f(i, m)) l = m;
			else r = m;
		}
		dq.back().l = l + 1;
		if(l >= 0) dq.pb(info(0, l, i));
	}
	for(int i = 0; i < n; i++) cout<<max(0LL, max(dpl[i] - h[i], dpr[i] - h[i]))<<"\n";

}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1668 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2396 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	2872 KB	Output is correct
2	Correct	26 ms	2140 KB	Output is correct
3	Correct	27 ms	2884 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	3964 KB	Output is correct
2	Correct	44 ms	3984 KB	Output is correct
3	Correct	45 ms	4520 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	9040 KB	Output is correct
2	Correct	106 ms	8604 KB	Output is correct
3	Correct	104 ms	8680 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	15436 KB	Output is correct
2	Correct	166 ms	13432 KB	Output is correct
3	Correct	164 ms	14112 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	21888 KB	Output is correct
2	Correct	253 ms	19096 KB	Output is correct
3	Correct	234 ms	19944 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	244 ms	19384 KB	Output is correct
2	Correct	235 ms	18916 KB	Output is correct
3	Correct	234 ms	20048 KB	Output is correct

Submission #874321

Compilation message