oj.uz

Submission #686540

# Submission time Handle Problem Language Result Execution time Memory
686540 2023-01-25T12:13:59 Z browntoad Lightning Conductor (POI11_pio) C++14
100 / 100
 162 ms 25652 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16864 KB Output is correct
2 Correct 24 ms 16340 KB Output is correct
3 Correct 29 ms 16976 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17364 KB Output is correct
2 Correct 40 ms 17324 KB Output is correct
3 Correct 30 ms 17464 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 19228 KB Output is correct
2 Correct 80 ms 18908 KB Output is correct
3 Correct 62 ms 18900 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 22820 KB Output is correct
2 Correct 109 ms 20824 KB Output is correct
3 Correct 86 ms 21608 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 25652 KB Output is correct
2 Correct 151 ms 22988 KB Output is correct
3 Correct 132 ms 23884 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 23396 KB Output is correct
2 Correct 162 ms 22792 KB Output is correct
3 Correct 119 ms 23856 KB Output is correct