oj.uz

Submission #621134

# Submission time Handle Problem Language Result Execution time Memory
621134 2022-08-03T12:49:09 Z Hanksburger Holiday (IOI14_holiday) C++17
100 / 100
 920 ms 17804 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 4 ms 6996 KB Output is correct
3 Correct 3 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 3 ms 6996 KB Output is correct
7 Correct 3 ms 6996 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 14680 KB Output is correct
2 Correct 649 ms 13112 KB Output is correct
3 Correct 688 ms 14828 KB Output is correct
4 Correct 647 ms 14680 KB Output is correct
5 Correct 920 ms 12784 KB Output is correct
6 Correct 292 ms 12028 KB Output is correct
7 Correct 450 ms 10588 KB Output is correct
8 Correct 525 ms 10860 KB Output is correct
9 Correct 266 ms 13260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7284 KB Output is correct
2 Correct 16 ms 7252 KB Output is correct
3 Correct 16 ms 7300 KB Output is correct
4 Correct 17 ms 7112 KB Output is correct
5 Correct 14 ms 7112 KB Output is correct
6 Correct 6 ms 7024 KB Output is correct
7 Correct 6 ms 6984 KB Output is correct
8 Correct 6 ms 6996 KB Output is correct
9 Correct 7 ms 7012 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 17804 KB Output is correct
2 Correct 801 ms 15864 KB Output is correct
3 Correct 279 ms 8704 KB Output is correct
4 Correct 13 ms 7124 KB Output is correct
5 Correct 6 ms 6996 KB Output is correct
6 Correct 6 ms 6996 KB Output is correct
7 Correct 5 ms 6996 KB Output is correct
8 Correct 882 ms 12476 KB Output is correct
9 Correct 854 ms 12480 KB Output is correct