Submission #37029

#	Time	Username	Problem	Language	Result	Execution time	Memory
37029		petil	Holiday (IOI14_holiday)	C++11	Compilation error	0 ms	0 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll vi[100005], Ldir[100005], Rdir[100005];
int n, st, d, po[100005];

struct BIT{
    vector<ll> tree;
    vector<int> cnt;
    BIT(){}
    BIT(int V):tree(4*V), cnt(4*V){}
    void update(int x, int L, int R, int idx, ll val, int flag){
        if(idx<L ||R<idx)return;
        if(L==R){
            cnt[x]+=flag;
            tree[x]+=flag*val;return;
        }
        int mid = (L+R)>>1;
        if(idx<=mid)update(x+x, L, mid, idx, val, flag);
        else update(x+x+1, mid+1, R, idx, val, flag);
        tree[x] = tree[x+x] + tree[x+x+1];
        cnt[x] = cnt[x+x] + cnt[x+x+1];
    }

    ll query(int x, int L, int R, int topk){
        if(topk==0)return 0;
        if(L==R){
            return tree[x];
        }
        int mid = (L+R)>>1;
        ll ret = 0;
        if(cnt[x+x]<topk){
            ret = tree[x+x];
            return ret + query(x+x+1, mid+1, R, topk-cnt[x+x]);
        }
        else{
            return query(x+x, L, mid, topk);
        }
    }

}bit;

void div_conq(int L, int R, int c1, int c2, ll dir[]){
    if(L>R){
        return;
    }
    if(c1==c2){
        bit.update(1,1, n, po[c1], vi[c1], 1);
        for(int i=L; i<=R; i++){
             int tp = i - (c1-st);
             tp = max(tp, 0);
             dir[i] =  bit.query(1, 1, n, tp);
        }

        bit.update(1, 1, n ,po[c1], vi[c1], -1);
        return;
    }

    int T = (L+R)>>1;

    ll ret = -1;
    int pos = -1;
    for(int i= c1; i<=c2; i++){
        int tp = T - (i-st);
        tp = max(tp, 0);


        bit.update(1, 1, n, po[i], vi[i], 1);

        ll ss = bit.query(1, 1, n, tp);
       if(ret < ss){
            ret = ss, pos = i;
       }

    }
    dir[T] = ret;
    for(int i=c1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], -1);

    if(L==R)return;

    div_conq(L, T-1, c1, pos,  dir);

    for(int i=c1; i<=pos-1; i++)bit.update(1, 1, n, po[i], vi[i], 1);

    div_conq(T+1, R, pos, c2, dir);

}
void div_conq2(int L, int R, int c1, int c2, ll dir[]){
    if(L>R){
        return;
    }
    if(c1==c2){
        bit.update(1,1, n, po[c1], vi[c1], 1);
        for(int i=L; i<=R; i++){
             int tp = i - 2*abs(c1-st);
             tp = max(tp, 0);
             dir[i] =  bit.query(1, 1, n, tp);
        }

        bit.update(1, 1, n ,po[c1], vi[c1], -1);
        return;
    }

    int T = (L+R)>>1;

    ll ret = -1;
    int pos = -1;
    for(int i= c2; i>=c1; i--){
        int tp = T - 2*abs(i-st);
        tp = max(tp, 0);
        bit.update(1, 1, n, po[i], vi[i], 1);

        ll ss = bit.query(1, 1, n, tp);
       if(ret < ss){
            ret = ss, pos = i;
       }
    }
    dir[T] = ret;
    for(int i=c1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], -1);

    if(L==R)return;

    div_conq2(L, T-1, pos, c2, dir);

    for(int i=pos+1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], 1);

    div_conq2(T+1, R, c1, pos, dir);
}
ll ans;
void go()
{
    bit = BIT(n+5);
    div_conq(1, d, st+1, n, Rdir);
    bit = BIT(n+5);
    div_conq2(1, d, 1, st-1, Ldir);
    for(int i=0; i<=d; i++){
        ans = max(ans, Ldir[i] + Rdir[d-i]);
        if(i!=d)
            ans = max(ans, Ldir[i] + Rdir[d-1-i] + vi[st]);
      //  cout<<i<<" " <<Ldir[i] <<" " <<Rdir[i]<<endl;
    }
}
int main()
{
    scanf("%d %d %d", &n, &st, &d);
    vector<pair<int, int> > tmp;
    for(int i=1; i<=n; i++){
        scanf("%lld", &vi[i]);
        tmp.push_back({-vi[i], i});
    }
    sort(tmp.begin(), tmp.end());
    for(int i=0; i<(int)tmp.size(); i++){
        po[tmp[i].second] = i+1;
    }
    go();
    tmp.clear();
    reverse(vi+1, vi+n+1);st = n+1-st;
    for(int i=1; i<=n; i++){
        tmp.push_back({-vi[i], i});
    }
    sort(tmp.begin(), tmp.end());
    for(int i=0; i<(int)tmp.size(); i++){
        po[tmp[i].second] = i+1;
    }
    go();
    cout<<ans;
}

Compilation message (stderr)

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