이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <algorithm>
#include <cstdio>
using namespace std;
struct node {
int cnt;
long long val;
void combine(const node &a, const node &b) {
cnt=a.cnt+b.cnt;
val=a.val+b.val;
}
};
node seg[400100];
int pos[100100];
int posinseg[100100];
int *val;
void update(int idx,int l,int r,int k,bool state) {
if (l+1==r) {
if (state) {
seg[idx].cnt=1;
seg[idx].val=val[pos[l]];
} else {
seg[idx].cnt=0;
seg[idx].val=0;
}
return;
}
int m=(l+r)>>1;
if (k<m) update(idx*2+1,l,m,k,state);
else update(idx*2+2,m,r,k,state);
seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}
long long query(int idx,int l,int r,int k) {
if (k<=0) return 0;
if (seg[idx].cnt<=k) return seg[idx].val;
if (l+1==r) return 0;
int m=(l+r)>>1;
if (seg[idx*2+1].cnt>=k) return query(idx*2+1,l,m,k);
return seg[idx*2+1].val+query(idx*2+2,m,r,k-seg[idx*2+1].cnt);
}
long long f[300100];
long long g[300100];
int fid[300100];
int gid[300100];
int st;
int N;
void findopt(int l,int r,int optl,int optr) {
if (l>r) return;
//[st,optl) has turned on
int mid=(l+r)>>1;
f[mid]=-1;
int optm=-1;
long long res;
for (int i=optl;i<=optr;i++) {
update(0,0,N,posinseg[i],true);
res=query(0,0,N,mid-i+st);
if (res>f[mid]) {
f[mid]=res;
optm=i;
}
}
fid[mid]=optm;
//turn [optm,optr] off
for (int i=optm;i<=optr;i++) {
update(0,0,N,posinseg[i],false);
}
findopt(mid+1,r,optm,optr);
//turn [optl,optm) off
for(int i=optl;i<optm;i++) {
update(0,0,N,posinseg[i],false);
}
findopt(l,mid-1,optl,optm);
}
void findopt2(int l,int r,int optl,int optr) {
if (l>r) return;
//(optr,st) has turned on
int mid=(l+r)>>1;
g[mid]=-1;
int optm=-1;
long long res;
for (int i=optr;i>=optl;i--) {
update(0,0,N,posinseg[i],true);
res=query(0,0,N,mid-st+i+1);
if (res>g[mid]) {
g[mid]=res;
optm=i;
}
}
gid[mid]=optm;
//turn [optl,optm] off
for (int i=optl;i<=optm;i++) {
update(0,0,N,posinseg[i],false);
}
findopt2(l,mid-1,optl,optm);
//turn (optm,optr] off
for(int i=optm+1;i<=optr;i++) {
update(0,0,N,posinseg[i],false);
}
findopt2(mid+1,r,optm,optr);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
val=attraction;
N=n;
st=start;
for (int i=0;i<n;i++) {
pos[i]=i;
}
sort(pos,pos+n,[attraction](const int &a, const int &b) {
return attraction[a]>attraction[b];
});
for (int i=0;i<n;i++) {
posinseg[pos[i]]=i;
}
findopt(0,d,st,n-1);
findopt2(0,d,0,st-1);
long long ans=f[d];
/*
for (int i=0;i<d;i++) {
//i to right: f[i]
if (d-i-fid[i]+st-1>0) {
ans=max(ans,f[i]+g[d-i-fid[i]+st-1]);
}
}
for (int i=0;i<d;i++) {
//i to left: g[i]
if (d-i-st+gid[i]-1>0) {
ans=max(ans,g[i]+f[d-i+gid[i]-st-1]);
}
}
*/
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^~~
# | 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... |