Submission #621134

#	Time	Username	Problem	Language	Result	Execution time	Memory
621134		Hanksburger	Holiday (IOI14_holiday)	C++17	100 / 100	920 ms	17804 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
long long seg[400005], cnt[400005], f[250005], ff[250005], g[250005], gg[250005], a[100005], c[100005], n, s, d, ans;
pair<long long, long long> b[100005];
void update(long long i, long long l, long long r, long long x, long long y)
{
//    cout << "update " << i << ' ' << l << ' ' << r << ' ' << x << ' ' << y << '\n';
    if (l==r)
    {
        seg[i]=y;
        cnt[i]=(bool)y;
        return;
    }
    long long mid=(l+r)/2;
    if (x<=mid)
        update(i*2, l, mid, x, y);
    else
        update(i*2+1, mid+1, r, x, y);
    seg[i]=seg[i*2]+seg[i*2+1];
    cnt[i]=cnt[i*2]+cnt[i*2+1];
}
long long query(long long i, long long l, long long r, long long x)
{
//    cout << "query " << i << ' ' << l << ' ' << r << ' ' << x << '\n';
    if (cnt[i]==x)
        return seg[i];
    long long mid=(l+r)/2;
    if (cnt[i*2]>=x)
        return query(i*2, l, mid, x);
    else
        return query(i*2, l, mid, cnt[i*2])+query(i*2+1, mid+1, r, x-cnt[i*2]);
}
long long query2(long long i, long long l, long long r, long long x)
{
//    cout << "query2 " << i << ' ' << l << ' ' << r << ' ' << x << '\n';
    if (cnt[i]==x)
        return seg[i];
    long long mid=(l+r)/2;
    if (cnt[i*2+1]>=x)
        return query2(i*2+1, mid+1, r, x);
    else
        return query2(i*2, l, mid, x-cnt[i*2+1])+query2(i*2+1, mid+1, r, cnt[i*2+1]);
}
void recur(long long l, long long r, long long ql, long long qr)
{
//    cout << "recur " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
    long long mid=(l+r)/2;
    for (long long i=ql; i<=qr; i++)
    {
        update(1, s, n-1, c[i], a[i]);
        if (1<=mid-i+s)
        {
            long long res=query(1, s, n-1, min(cnt[1], mid-i+s));
            if (ff[mid]<res)
            {
                ff[mid]=res;
                f[mid]=i;
            }
        }
    }
    for (long long i=ql; i<=qr; i++)
        update(1, s, n-1, c[i], 0);
    if (l<mid)
        recur(l, mid-1, ql, f[mid]);
    if (mid<r)
        recur(mid+1, r, f[mid], qr);
    for (long long i=ql; i<=qr; i++)
        update(1, s, n-1, c[i], a[i]);
}
void recur2(long long l, long long r, long long ql, long long qr)
{
//    cout << "recur2 " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
    long long mid=(l+r)/2;
    for (long long i=qr; i>=ql; i--)
    {
        update(1, 0, s-1, c[i], a[i]);
        if (1<=mid-s+i+1)
        {
            long long res=query2(1, 0, s-1, min(cnt[1], mid-s+i+1));
            if (gg[mid]<res)
            {
                gg[mid]=res;
                g[mid]=i;
            }
        }
    }
    for (long long i=qr; i>=ql; i--)
        update(1, 0, s-1, c[i], 0);
    if (l<mid)
        recur2(l, mid-1, g[mid], qr);
    if (mid<r)
        recur2(mid+1, r, ql, g[mid]);
    for (long long i=qr; i>=ql; i--)
        update(1, 0, s-1, c[i], a[i]);
}
long long findMaxAttraction(int N, int S, int D, int A[])
{
    if (!D)
        return 0;
    n=N;
    s=S;
    d=D;
    for (long long i=0; i<n; i++)
    {
        a[i]=A[i];
        b[i]={a[i], i};
    }
    sort(b, b+s);
    sort(b+s, b+n, greater<pair<long long, long long> >());
    for (long long i=0; i<n; i++)
        c[b[i].second]=i;
    for (long long i=0; i<=d; i++)
    {
        f[i]=s;
        g[i]=s-1;
    }
    if (s<n)
        recur(1, d, s, n-1);
    for (long long i=0; i<=4e5; i++)
        seg[i]=cnt[i]=0;
    if (s)
        recur2(1, d, 0, s-1);
//    cout << "f: ";
//    for (long long i=0; i<=d; i++)
//        cout << f[i] << ' ';
//    cout << '\n';
//    cout << "ff: ";
//    for (long long i=0; i<=d; i++)
//        cout << ff[i] << ' ';
//    cout << '\n';
//    cout << "g: ";
//    for (long long i=0; i<=d; i++)
//        cout << g[i] << ' ';
//    cout << '\n';
//    cout << "gg: ";
//    for (long long i=0; i<=d; i++)
//        cout << gg[i] << ' ';
//    cout << '\n';
    ans=max(ff[d], gg[d-1]);
    for (long long i=0; i<=d; i++)
    {
        if (d-i-f[i]+s-1>=0)
            ans=max(ans, ff[i]+gg[d-i-f[i]+s-1]);
        if (d-i-s+g[i]-1>=0)
            ans=max(ans, gg[i]+ff[d-i-s+g[i]-1]);
    }
    return ans;
}

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