Submission #799187

#	Time	Username	Problem	Language	Result	Execution time	Memory
799187		FatihSolak	Holiday (IOI14_holiday)	C++17	100 / 100	416 ms	19472 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define N 300005
using namespace std;
struct BIT{
    vector<pair<int,long long>> bit;
    int n;
    BIT(int sz){
        n = sz + 5;
        bit.assign(n,{0,0});
    }
    void upd(int pos,int val1,int val2){
        for(;pos < n;pos += pos & - pos){
            bit[pos].first += val1;
            bit[pos].second += val2;
        }
    }
    long long get(int k){
        long long ret = 0;
        int pos = 0;
        for(int i = 20;i>=0;i--){
            if((pos + (1<<i )) >= n)continue;
            if(bit[pos + (1<<i)].first <= k){
                ret += bit[pos + (1<<i)].second;
                k -= bit[pos + (1<<i)].first;
                pos += (1<<i);
            }
        }
        return ret;
    }
}bt(N);

int val[N];
int ord[N];
long long ans[N];
int cur = 0;
void solve(int l,int r,int optl,int optr,int x){
    if(r < l)
        return;
    while(cur < optl){
        cur++;
        bt.upd(ord[cur],1,val[ord[cur]]);
    }
    while(cur > optl){
        bt.upd(ord[cur],-1,-val[ord[cur]]);
        cur--;
    }
    int m = (l + r)/2;
    int opt = -1;
    ans[m] = -1;
    int now = (optl) * x;
    for(int i = optl;i <= optr;i++){
        if(now > m)break;
        long long tmp = bt.get(m - now);
        if(tmp > ans[m]){
            ans[m] = tmp;
            opt = i;
        }
        now += x;
        if(i != optr){
            cur++;
            bt.upd(ord[cur],1,val[ord[cur]]);
        }
    }
    solve(l,m-1,optl,opt,x);
    solve(m+1,r,opt,optr,x);
}
vector<long long> get(int d,int x,vector<int> a){
    int n = a.size();
    for(int i = 0;i<n;i++){
        ord[i + 1] = a[i]; 
    }
    solve(0,d,0,n,x);
    while(cur > 0){
        bt.upd(ord[cur],-1,-val[ord[cur]]);
        cur--;
    }
    vector<long long> ret;
    for(int i = 0;i<=d;i++){
        ret.push_back(ans[i]);
    }
    return ret;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans = 0;
    vector<int> tmp;
    for(int i = 0;i<n;i++){
        tmp.push_back(i);
    }
    sort(tmp.begin(),tmp.end(),[&](int a,int b){
        return attraction[a] > attraction[b];
    });
    vector<int> ord(n);
    for(int i = 0;i<n;i++){
        ord[tmp[i]] = i + 1;
        val[i + 1] = attraction[tmp[i]];
    }
    vector<int> l,r;
    for(int i = start-1;i>=0;i--){
        l.push_back(ord[i]);
    }
    for(int i = start + 1;i<n;i++){
        r.push_back(ord[i]);
    }
    auto l1 = get(d,1,l);
    auto l2 = get(d,2,l);
    auto r1 = get(d,1,r);
    auto r2 = get(d,2,r);
    ans = max(ans,l1[d]);
    ans = max(ans,r1[d]);
    // cout << ans << endl;
    // for(auto u:l1){
    //     cout << u << ' ';
    // }
    // cout << endl;
    // for(auto u:l2){
    //     cout << u << ' ';
    // }
    // cout << endl;
    // for(auto u:r1){
    //     cout << u << ' ';
    // }
    // cout << endl;
    // for(auto u:r2){
    //     cout << u << ' ';
    // }
    // cout << endl;
    for(int xx = 0;xx < 2;xx++){
        d -= xx;
        int add = 0;
        if(xx)
            add = attraction[start];
        for(int i = 0;i<=d;i++){
            ans = max(ans,l1[d-i] + r2[i] + add);
            // cout << i << ' ' << ans << endl;
            ans = max(ans,r1[d-i] + l2[i] + add);
            // cout << i << ' ' << ans << endl;
        }
    }
    return ans;
}

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