Submission #854816

#	Time	Username	Problem	Language	Result	Execution time	Memory
854816		12345678	Holiday (IOI14_holiday)	C++17	0 / 100	27 ms	8284 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll id[nx];
ll ans;

struct segtree
{
    ll f[4*nx];
    ll sm[4*nx];
    void update(int l, int r, int i, int idx, ll val)
    {
        if (idx<l||r<idx) return void();
        if (l==r) return f[i]=1, sm[i]=val, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, val);
        update(md+1, r, 2*i+1, idx, val);
        f[i]=f[2*i]+f[2*i+1];
        sm[i]=sm[2*i]+sm[2*i+1];
    }
    ll query(int l, int r, int i, int cnt)
    {
        if (l==r) return (cnt==1)?sm[i]:0;
        int md=(l+r)/2;
        if (f[2*i]>cnt) return query(l, md, 2*i, cnt);
        return sm[2*i]+query(md+1, r, 2*i+1, cnt-f[2*i]);
    }
} s;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<pair<ll, ll>> v(n);
    for (int i=0; i<n; i++) v[i]={attraction[i], i};
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for (int i=0; i<n; i++) id[v[i].second]=i;
    for (int i=0; i<n; i++)
    {
        s.update(0, n-1, 1, id[i], attraction[i]);
        ans=max(ans, s.query(0, n-1, 1, d-i));
    }
    return ans;
}

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