Submission #37082

#	Time	Username	Problem	Language	Result	Execution time	Memory
37082		petil	Holiday (IOI14_holiday)	C++14	100 / 100	1879 ms	20064 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Ldir[350005], Rdir[350005], ans;
int n, st, d, vi[100005], po[100005];
struct BIT{
    vector<int> cnt;
    vector<ll>tree;
    BIT(){}
    BIT(int V) :cnt(4*V), tree(4*V){
        fill(cnt.begin(), cnt.end() ,0);
        fill(tree.begin(), tree.end(), 0);
    }
    void update(int x, int L, int R, int idx, int val){
        if(idx<L || R < idx)return;
        if(L==R && L==idx){
            if(val<0){
                cnt[x] = tree[x] = 0;
            }
            else{
                cnt[x] =1 ;tree[x] = val;
            }
            return;
        }
        int mid = (L+R)>>1;
        if(idx <=mid) update(x+x, L, mid, idx, val);
        else update(x+x+1, mid+1, R, idx, val);
        cnt[x] = cnt[x+x] + cnt[x+x+1];
        tree[x] = tree[x+x] + tree[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;
        if(cnt[x+x] <=topk){
            return tree[x+x] + query(x+x+1, mid+1, R, topk - cnt[x+x]);
        }
        else{
            return query(x+x, L, mid, topk);
        }
    }
}bit;
void dp1(int LT, int RT, int c1, int c2, ll dir[])
{
    if(LT>RT)return;
    int T = (LT+RT)>>1;
    dir[T] = -1;
    int cc = -1;
    for(int i=c1; i<=c2; i++){
        bit.update(1, 1, n, po[i], vi[i]);
        int tp = T - (i-st);
        tp = max(tp, 0);
        ll ss = bit.query(1, 1, n, tp);
        if(dir[T] < ss){
            dir[T] = ss;    cc = i;
        }
    }

    for(int i=c1; i<=c2; i++)bit.update(1,1, n, po[i], -1);
    if(LT==RT)return;

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

}
void dp2(int LT, int RT, int c1, int c2, ll dir[]){
    if(LT>RT)return;
    int T = (LT+RT)>>1;
    dir[T] = -1;
    int cc = -1;
    for(int i=c1; i>=c2; i--){
        bit.update(1, 1, n, po[i], vi[i]);
        int tp = T - 2*(st-i);
        tp = max(tp, 0);
        ll ss = bit.query(1, 1, n, tp);
        if(dir[T] < ss){
            dir[T]= ss; cc = i;
        }
    }
    for(int i=c1; i>=c2; i--){
        bit.update(1, 1, n, po[i], -1);
    }

    dp2(LT, T-1, c1, cc, dir);
    for(int i=c1; i>cc; i--){
        bit.update(1, 1, n, po[i], vi[i]);
    }
    dp2(T+1, RT, cc, c2, dir);
    for(int i=c1; i>cc; i--){
        bit.update(1, 1, n, po[i], -1);
    }

}
void go()
{
    vector<pair<int, int> >tmp;
    for(int i=1 ;i<=n; i++){
        tmp.push_back({-vi[i], i});
    }
    sort(tmp.begin(), tmp.end());
    for(int i=0; i<tmp.size() ;i++){
        po[tmp[i].second] = i+1;
    }
    bit = BIT(n+5);
    dp1(1, d, st, n, Rdir);
    
    if(st>1){
        bit = BIT(n+5);
        dp2(1, d, st-1, 1, Ldir);
    }
    else{
        for(int i=0; i<=d; i++)Ldir[i] = 0;
    }
    for(int i=0; i<=d; i++){
        ans = max(ans, Ldir[i] + Rdir[d-i]);
      ///  cout<<i<<" " <<Ldir[i] <<" "<< Rdir[i]<<endl;
    }
}
//FILE *fi = freopen("sample-4.in", "r", stdin);
ll findMaxAttraction(int N, int start, int dd, int attr[]){
    n = N;
    st = start;++st;
    d = dd;
    for(int i=0; i<n; i++){
        vi[i+1] = attr[i];
    }
    ans=0;
    
    go();
    reverse(vi+1, vi+n+1);
    st = n+1- st;
    go();
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void go()':
holiday.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<tmp.size() ;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;
            ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53