Submission #582345

#	Time	Username	Problem	Language	Result	Execution time	Memory
582345		jasmin	Holiday (IOI14_holiday)	C++14	47 / 100	5043 ms	10156 KiB

holiday

#include<bits/stdc++.h>
#include<holiday.h>
using namespace std;
#define int long long

struct segtree{
    vector<pair<int,int> > tree;

    segtree(int n){
        tree.resize(n*4);
    }

    pair<int,int> merge(pair<int,int> a, pair<int,int> b){
        return {a.first+b.first, a.second+b.second};
    }

    pair<int,int> update(int l, int r, int v, int x, int val, bool add){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]={add, val};
        }
        int m=l+(r-l)/2;
        return tree[v]=merge(update(l, m, v*2+1, x, val, add), update(m, r, v*2+2, x, val, add));
    }
    pair<int,int> query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return {0, 0};
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

int bestk(int d, segtree& seg, int n){
    if(d<=0) return 0;

    int l=0; int r=n;
    int ans=0;
    while(l<=r){
        int m=l+(r-l)/2;
        auto val=seg.query(0, n, 0, 0, m);
        if(val.first<=d){
            ans=val.second;
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    return ans;
}

long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
    vector<int> ind(n);
    vector<pair<int,int> > sorted(n);
    for(int i=0; i<n; i++){
        sorted[i]={attraction[i], i};
    }
    sort(sorted.begin(), sorted.end());
    reverse(sorted.begin(), sorted.end());
    for(int i=0; i<n; i++){
        ind[sorted[i].second]=i;
    }

    int ans=0;
    segtree seg(n);
    for(int l=start; l>=0; l--){
        seg.update(0, n, 0, ind[l], attraction[l], true);
        for(int r=start; r<n; r++){
            if(r!=start){
                seg.update(0, n, 0, ind[r], attraction[r], true);
            }

            int days=d-(r-l+min(r-start, start-l));
            if(0<days){
                ans=max(ans, bestk(days, seg, n));
            }
        }
        for(int r=start+1; r<n; r++){
            seg.update(0, n, 0, ind[r], 0, false);
        }
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int32_t n, start, d;
    cin >> n >> start >> d;
    int32_t a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    cout << findMaxAttraction(n, start, d, a) << "\n";
}*/

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