Submission #686540

#	Time	Username	Problem	Language	Result	Execution time	Memory
686540		browntoad	Lightning Conductor (POI11_pio)	C++14	100 / 100	162 ms	25652 KiB

pio

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=5e5+5;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}

//=======================================================================================

int n;
vector<int> ans(maxn), vc(maxn);
long double eps = 0.000000001;
vector<long double> sq(maxn);
long double val(int x, int comp){
	// x will be compared with comp
	if (x==comp){
		return vc[comp];
	}
	if (x>comp){
		// comp is on the left
		return sq[x-comp]+vc[comp];
	}
	else {
		return sq[comp-x]+vc[comp];
	}
}
void run(int l, int r, int ql, int qr, bool wh){
	if (qr<ql||ql<=0||qr>n){
		return;
	}
	pair<long double, int> cur = {0.0, 0};
	int mid = (ql+qr) >> 1;
	int k;
	FOR(i, l, r+1){
		if (wh==0) if (i>mid) continue;
		if (wh==1) if (i<mid) continue;
		if (val(mid, i) > cur.f){
			cur.f=val(mid, i);
			cur.s=i;
		}
	}
	k=cur.f;
	if (0.0 + cur.f - k >= eps){
		k++;
	}
	ans[mid] = max(ans[mid], k);
	run(l, cur.s, ql, mid-1, wh);
	run(cur.s, r, mid+1, qr, wh);
	
}

signed main (){
    IOS();
    cin>>n;
    REP1(i, n){
    	cin>>vc[i];
    }
    REP(i, n+1){
    	sq[i]=sqrtl(i);
    }
    FOR(k, 0, 2){
    	run(1, n, 1, n, k);
    }
    REP1(i, n){
    	cout<<ans[i]-vc[i]<<endl;
    }

}
// 44 min

• 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