oj.uz

Submission #892289

# Submission time Handle Problem Language Result Execution time Memory
892289 2023-12-25T06:53:42 Z 12345678 Holiday (IOI14_holiday) C++17
100 / 100
 1144 ms 19172 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, dx=250005;

int id[nx], st, N, D;
ll ans, dp[4][dx];
vector<pair<ll, int>> v;

struct segtree
{
    int f[4*nx];
    ll sm[4*nx];
    void build(int l, int r, int i)
    {
        f[i]=sm[i]=0;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, ll val)
    {
        if (idx<l||r<idx) return;
        if (l==r) 
        {
            if (val>=0) return f[i]=1, sm[i]=val, void();
            else return f[i]=sm[i]=0, 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 (cnt>=f[i]) return sm[i];
        if (cnt<=0) return 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;

void solver(int st, int ml, int sl)
{
    int lst=st-1+(ml==2);
    queue<tuple<int, int, int, int>> q;
    q.push({0, D, st+(ml==2), N-1});
    if ((st+(ml==2))>N-1) return;
    while (!q.empty())
    {
        auto [l, r, optl, optr]=q.front();
        q.pop();
        if (r<l) continue;
        int md=(l+r+1)/2;
        pair<ll, int> p={-1, -1};
        for (int i=optl; i<=optr; i++)
        {
            while (lst<i) ++lst, s.update(0, N-1, 1, id[lst], v[id[lst]].first);
            while (lst>i) s.update(0, N-1, 1, id[lst], -1), lst--;
            p=max(p, make_pair(s.query(0, N-1, 1, md-ml*(i-st)), i));
        }
        dp[sl][md]=p.first;
        q.push({l, md-1, optl, p.second});
        q.push({md+1, r, p.second, optr});
    }
    s.build(0, N-1, 1);
}

void solvel(int st, int ml, int sl)
{
    int lst=st+1-(ml==2);
    queue<tuple<int, int, int, int>> q;
    q.push({0, D, 0, st-(ml==2)});
    if ((st-(ml==2))<0) return;
    while (!q.empty())
    {
        auto [l, r, optl, optr]=q.front();
        q.pop();
        if (r<l) continue;
        int md=(l+r)/2;
        pair<ll, int> p={0, optl};
        for (int i=optl; i<=optr; i++)
        {
            while (lst>i) --lst, s.update(0, N-1, 1, id[lst], v[id[lst]].first);
            while (lst<i) s.update(0, N-1, 1, id[lst], -1), lst++;
            p=max(p, make_pair(s.query(0, N-1, 1, md-ml*(st-i)), i));
        }
        dp[sl][md]=p.first;
        q.push({l, md-1, p.second, optr});
        q.push({md+1, r, optl, p.second});
    }
    s.build(0, N-1, 1);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    v.resize(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;
    N=n; D=d; st=start;
    solver(st, 1, 0);
    solver(st, 2, 1);
    solvel(st, 1, 2);
    solvel(st, 2, 3);
    for (int i=0; i<=D; i++) ans=max(ans, dp[0][i]+dp[3][D-i]);
    for (int i=0; i<=D; i++) ans=max(ans, dp[1][i]+dp[2][D-i]);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 9052 KB Output is correct
4 Correct 1 ms 9048 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1 ms 11100 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 15232 KB Output is correct
2 Correct 598 ms 15444 KB Output is correct
3 Correct 710 ms 15524 KB Output is correct
4 Correct 648 ms 15696 KB Output is correct
5 Correct 874 ms 15120 KB Output is correct
6 Correct 274 ms 11892 KB Output is correct
7 Correct 467 ms 13392 KB Output is correct
8 Correct 546 ms 13348 KB Output is correct
9 Correct 198 ms 15064 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9052 KB Output is correct
2 Correct 20 ms 9052 KB Output is correct
3 Correct 20 ms 9248 KB Output is correct
4 Correct 18 ms 11100 KB Output is correct
5 Correct 19 ms 11100 KB Output is correct
6 Correct 5 ms 11100 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 6 ms 11556 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 19164 KB Output is correct
2 Correct 787 ms 19172 KB Output is correct
3 Correct 354 ms 14152 KB Output is correct
4 Correct 15 ms 11096 KB Output is correct
5 Correct 5 ms 11100 KB Output is correct
6 Correct 6 ms 11100 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 1138 ms 16620 KB Output is correct
9 Correct 1139 ms 16628 KB Output is correct