제출 #874321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874321		phoenix0423	새로운 문제 (POI11_pio)	C++17	100 / 100	253 ms	21888 KiB

pio

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10