This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<holiday.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,k,x,y,a[maxn],cur,S,opt[maxn],dp[maxn][3][2];
vector<int> v;
struct node
{
vector<int> a;
vector<int> pfs;
int l,r;
}ST[maxn*30];
void cons(int id,vector<int> v,int lval,int rval)
{
if(v.size()==0) return;
int mid=(lval+rval)/2;
vector<int> s[2];
ST[id].a.push_back(0);
ST[id].pfs.push_back(0);
for(int i:v)
{
int cc=ST[id].a.back()+(a[i]>mid);
ST[id].a.push_back(cc);
s[a[i]>mid].push_back(i);
cc=ST[id].pfs.back()+(a[i]>mid)*a[i];
ST[id].pfs.push_back(cc);
}
v.clear();
if(rval==lval) return;
if(s[0].size()) cons(ST[id].l=++cur,s[0],lval,mid);
if(s[1].size()) cons(ST[id].r=++cur,s[1],mid+1,rval);
}
int get(int id,int k,int l,int r,int lval,int rval)
{
if(id==0||ST[id].a.size()<=1||k<=0) return 0;
if(lval==rval)
{
return min(k,(int)ST[id].a.size())*lval;
}
int mid=(lval+rval)/2;
int s1=ST[id].a[l-1];
int s2=ST[id].a[r];
if(s2-s1>k)
{
return get(ST[id].r,k,s1+1,s2,mid+1,rval);
}
else
{
int cnt=ST[id].pfs[r]-ST[id].pfs[l-1];
return cnt+get(ST[id].l,k-(s2-s1),l-s1,r-s2,lval,mid);
}
}
void dnc(int l,int r,int optl,int optr,int rev,int jump)
{
if(l>r) return;
int mid=(l+r)/2;
opt[mid]=optl,dp[mid][jump][rev]=0;
for(int i=optl;i<=optr;i++)
{
if(!rev)
{
int dd=i-S;
int cc=get(1,mid-dd*jump,S+1,i,1,1e9);
if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
}
if(rev)
{
int dd=S-i;
int cc=get(1,mid-dd*jump,i,S-1,1,1e9);
if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
}
}
if(l==r) return;
if(!rev)
{
dnc(l,mid-1,optl,opt[mid],rev,jump);
dnc(mid+1,r,opt[mid],optr,rev,jump);
}
if(rev)
{
dnc(l,mid-1,opt[mid],optr,rev,jump);
dnc(mid+1,r,optl,opt[mid],rev,jump);
}
}
long long findMaxAttraction(int32_t n,int32_t start,int32_t d,int32_t b[])
{
for(int i=1;i<=n;i++) v.push_back(i);
for(int i=0;i<n;i++) a[i+1]=b[i];
cons(1,v,1,1e9);
S=start;
dnc(1,d,1,S-1,1,1);
dnc(1,d,1,S-1,1,2);
dnc(1,d,S+1,n,0,1);
dnc(1,d,S+1,n,0,2);
int ans=0;
for(int i=0;i<=d;i++)
{
ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
if(i<d)
{
ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
}
}
return ans;
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// int a[]={10,2,20,30,1};
// cout<<findMaxAttraction(5,2,7,a);
//}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |