oj.uz

Submission #392054

# Submission time Handle Problem Language Result Execution time Memory
392054 2021-04-20T10:43:24 Z Aldas25 Holiday (IOI14_holiday) C++14
100 / 100
 2410 ms 15564 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<int> vi;

const int MAXN = 500100;

ll a[MAXN];
int n, start;

vector<pair<ll, int>> srt;
int to[MAXN];

ll tree[4*MAXN], cnt[4*MAXN];

void build (int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        tree[id] = 0;
        cnt[id] = 0;
        return;
    }
    int mid = (le+ri)/2;
    build (2*id, le, mid);
    build (2*id+1, mid+1, ri);
    tree[id] = tree[2*id] + tree[2*id+1];
    cnt[id] = cnt[2*id] + cnt[2*id+1];
}

void turn (bool on, int p, int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        if (on) {
            tree[id] = srt[le].f;
            cnt[id] = 1;
        } else {
            tree[id] = 0;
            cnt[id] = 0;
        }
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        turn (on, p, 2*id, le, mid);
    else
        turn (on, p, 2*id+1, mid+1, ri);
    tree[id] = tree[2*id] + tree[2*id+1];
    cnt[id] = cnt[2*id] + cnt[2*id+1];
}

void turnOn (int p) {
    p = to[p];
    turn (1, p);
}

void turnOff (int p) {
    p = to[p];
    turn (0, p);
}

ll get (int x, int id = 1, int le = 0, int ri = n-1) {
    if (x <= 0) return 0;
    if (cnt[id] <= x) return tree[id];
    int mid = (le+ri)/2;
    return get(x, 2*id, le, mid) + get(x-cnt[2*id], 2*id+1, mid+1, ri);
}

ll f[MAXN], ansF[MAXN];
ll g[MAXN], ansG[MAXN];

void rec (int le, int ri, int fr, int to, int moved = 0) {
    int m = (le+ri)/2;
    ansF[m] = -1;
    FOR(i, fr, to) {
        int remD = m - moved - (i-fr);
        if (remD <= 0) break;
        turnOn(i);
        ll cur = get(remD);
        if (cur > ansF[m]) {
            ansF[m] = cur;
            f[m] = i;
        }
    }

    if (ansF[m] == -1) {
        ansF[m] = 0;
        f[m] = fr;
    }

    FOR(i, fr, to) turnOff(i);

    if (le <= m-1) rec(le, m-1, fr, f[m], moved);

    FOR(i, fr, f[m]-1) {
        moved++;
        turnOn(i);
    }
    if (m+1 <= ri) rec(m+1, ri, f[m], to, moved);
    FOR(i, fr, f[m]-1) {
        moved--;
        turnOff(i);
    }
}

void doSwap () {
    FOR(i, 0, n/2 - 1) {
        swap(a[i], a[n-i-1]);
        swap(to[i], to[n-i-1]);
    }
    start = n-1-start;
}

long long int findMaxAttraction(int N, int st, int d, int attraction[]) {
    n = N;
    start = st;
    FOR(i, 0, n-1) a[i] = attraction[i];

    FOR(i, 0, n-1) {
        srt.pb({a[i], i});
    }
    sort(srt.begin(), srt.end());
    reverse(srt.begin(), srt.end());

    FOR(i, 0, n-1) {
        to[srt[i].s] = i;
    }

    ll ans = 0;

    REP(2) {

        FOR(i, 0, d) {
            ansF[i] = ansG[i] = 0;
            f[i] = start;
            g[i] = start-1;
        }

        build ();

        doSwap();
        if (start+1 <= n-1) rec(0, d, start+1, n-1);
        doSwap();
       /* FOR(i, 0, d) {
            cout << " i = " << i  << endl;
            cout << "  f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;
            cout << "  g(i) = " << g[i] << " ansG(i) = " << ansG[i] << endl;
        } */

        FOR(i, 0, d) f[i] = n-1-f[i];
        FOR(i, 0, d) {
            g[i] = f[i];
            ansG[i] = ansF[i];
        }

        build ();
        FOR(i, 0, d) {
            ansF[i] = 0;
            f[i] = start;
        }

        rec(0, d, start, n-1);

        FOR(d0, 0, d) {
            int rem = d - d0 - (f[d0]-start) - 1;
            if (rem < 0) break;
            ll cur = ansF[d0] + ansG[rem];
            ans = max(ans, cur);
        }

       /* FOR(i, 0, d) {
            cout << " i = " << i  << endl;
            cout << "  f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;
            cout << "  g(i) = " << g[i] << " ansG(i) = " << ansG[i] << endl;
        } */

        doSwap();
    }

    //FOR(i, 0, d) cout << " i = " << i << " f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;

    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2020 ms 13952 KB Output is correct
2 Correct 1305 ms 13876 KB Output is correct
3 Correct 1988 ms 13884 KB Output is correct
4 Correct 1315 ms 13972 KB Output is correct
5 Correct 2326 ms 11444 KB Output is correct
6 Correct 781 ms 8004 KB Output is correct
7 Correct 1219 ms 6896 KB Output is correct
8 Correct 1394 ms 7104 KB Output is correct
9 Correct 606 ms 9540 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 964 KB Output is correct
2 Correct 33 ms 844 KB Output is correct
3 Correct 33 ms 868 KB Output is correct
4 Correct 34 ms 716 KB Output is correct
5 Correct 32 ms 748 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 7 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2003 ms 15564 KB Output is correct
2 Correct 2258 ms 15548 KB Output is correct
3 Correct 494 ms 4160 KB Output is correct
4 Correct 22 ms 588 KB Output is correct
5 Correct 6 ms 452 KB Output is correct
6 Correct 7 ms 460 KB Output is correct
7 Correct 7 ms 464 KB Output is correct
8 Correct 2410 ms 10032 KB Output is correct
9 Correct 2320 ms 10028 KB Output is correct