Submission #31150

#TimeUsernameProblemLanguageResultExecution timeMemory
31150dongwon0427Holiday (IOI14_holiday)C++11
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,st,d,Aidx[100005];
struct seg {
    ll val;
    int gaesu;
    seg operator + (const seg &a) const {
        seg ret;
        ret.val = val + a.val; ret.gaesu=gaesu + a.gaesu;
        return ret;
    }
};
struct _tuple {int idx;ll val;};
seg segtree[400005];
_tuple A[100005];
void updt(int idx,int s,int e,int x,seg key) {
    segtree[idx] = segtree[idx] + key;
    if(s==e) return;
    if(s<=x && x<=(s+e)/2) updt(idx*2,s,(s+e)/2,x,key);
    else updt(idx*2+1,(s+e)/2+1,e,x,key);
}
ll ksum(int idx,int s,int e,int k) {
    if(k<=0) return 0ll;
    if(k >= segtree[idx].gaesu) return segtree[idx].val;
    if(s==e) {
        if(segtree[idx].gaesu==0 || k<=0) return 0ll;
        return segtree[idx].val;
    }
    if( segtree[idx*2].gaesu < k ) return segtree[idx*2].val + ksum(idx*2+1,(s+e)/2+1,e,k-segtree[idx*2].gaesu);
    return ksum(idx*2,s,(s+e)/2,k);
}
ll dodp(int s,int e,int p,int q) {
    if(s>e) return 0;
    int m = (s+e)/2;
    for(int i=m;i<=e;i++) {
        seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    int v=p; ll _max = 0;
    for(int i=p;i<=q;i++) {
        seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
        ll tmpm = ksum(1,0,n-1,d - 2*(i-st) - (st-m));
        if(_max < tmpm) {
            v = i;
            _max = tmpm;
        }
    }
    for(int i=v;i<=q;i++) {
        seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    for(int i=m;i<=e;i++) {
        seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    ll ret1 = dodp(m+1,e,v,q);
    for(int i=p;i<v;i++) {
        seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    for(int i=m;i<=e;i++) {
        seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    ll ret2 = dodp(s,m-1,p,v);
    for(int i=m;i<=e;i++) {
        seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    ll ret = max({ret1,ret2,_max});
    return ret;
}
ll straight(int idx) {
    ll ret = 0;
    for(int i=idx;i<n;i++) {
        seg tmp; tmp.val = A[i].val; tmp.gaesu = 1;
        updt(1,0,n-1,Aidx[i],tmp);
        ret = max(ret,ksum(1,0,n-1,d - 2*(i-idx)));
    }
    for(int i=idx;i<n;i++) {
        seg tmp; tmp.val = -A[i].val; tmp.gaesu = -1;
        updt(1,0,n-1,Aidx[i],tmp);
    }
    return ret;
}
int main() {
    scanf("%d%d%d",&n,&st,&d);
    for(int i=0;i<n;i++) {
        scanf("%lld",&A[i].val);
        A[i].idx=i;
    }
    sort(A,A+n,[](_tuple a,_tuple b){return a.val > b.val;});
    for(int i=0;i<n;i++) Aidx[A[i].idx]=i;
    sort(A,A+n,[](_tuple a,_tuple b){return a.idx<b.idx;});
    ll ans1 = dodp(0,st-1,st,n-1);
    ll ans3 = straight(st);
    sort(A,A+n,[](_tuple a,_tuple b){return a.idx>b.idx;});
    for(int i=0;i<n/2;i++) swap(Aidx[i], Aidx[n-1-i]);
    ll ans2 = dodp(0,n-st-2,n-st-1,n-1);
    ll ans4 = straight(n-st-1);
    printf("%lld\n",max({ans1,ans2,ans3,ans4}));
    return 0;
}

Compilation message (stderr)

holiday.cpp: In function 'int main()':
holiday.cpp:89:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&st,&d);
                              ^
holiday.cpp:91:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&A[i].val);
                                ^
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;
            ^
/tmp/cct2GrbV.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc8irCFO.o:holiday.cpp:(.text.startup+0x0): first defined here
/tmp/cct2GrbV.o: In function `main':
grader.cpp:(.text.startup+0x7a): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status