oj.uz

Submission #438652

# Submission time Handle Problem Language Result Execution time Memory
438652 2021-06-28T11:08:23 Z prvocislo Holiday (IOI14_holiday) C++17
100 / 100
 465 ms 7868 KB 
#include "holiday.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5, maxd = 1 << 17;
//const int maxn = 8, maxd = 8;
ll st[2][maxd * 2];
ll a[maxn]; int id[maxn], n, s, d; // atrakcie a ich indexy v striedenom poli
void upd(int t, int i, int val)
{
    for (i += maxd; i > 0; i >>= 1) 
        st[t][i] += val;
}
void change(int i, int delta)
{
    upd(0, id[i], delta), upd(1, id[i], delta * a[i]);
}
ll max_k(int k)
{
    if (k <= 0) return 0;
    int vr = 2; ll ans = 0;
    for (;; vr = vr * 2) 
    {
        if (k > st[0][vr])
        {
            k -= st[0][vr];
            ans += st[1][vr];
            vr++;
        }
        if (vr >= maxd) return ans + st[1][vr];
    }//return ans + st[1][vr];
}
int L, R; // interval (vratane) ktory ma teraz obsadeny divide&conquer procedura
ll query(int l, int r) // nahod vsetky cisla v intervale l az r, najprv pojdeme doprava, potom sa otocime a pojdeme dolava
{
    while (L > l) change(--L, 1);
    while (R < r) change(++R, 1);
    while (L < l) change(L++, -1);
    while (R > r) change(R--, -1);
    return max_k(d - (r - l) - (r - s));
}
ll ans = 0;
void rek(int l, int r, int optl, int optr)
{
    if (r < l) return;
    int m = (l + r) >> 1;
    int maxid = m; ll maxi = -1;
    for (int i = optl; i <= optr; i++)
    {
        ll val = query(i, m);
        if (val >= maxi) maxi = val, maxid = i;
    }
    ans = max(ans, maxi);
    rek(l, m - 1, optl, maxid), rek(m + 1, r, maxid, optr);
}
long long int findMaxAttraction(int N, int S, int D, int A[]) {
    memset(st, 0, sizeof(st)), memset(a, 0, sizeof(a)), memset(id, 0, sizeof(id));
    n = N, s = S, d = D; ans = 0;
    vector<pair<int, int> > v;
    for (int i = 0; i < n; i++) a[i] = A[i], v.push_back({a[i], i});
    sort(v.begin(), v.end(), greater<pair<int, int> >());
    for (int i = 0; i < n; i++) id[v[i].second] = i;
    L = 0, R = -1;
    rek(s, n - 1, 0, s);
    reverse(a, a + n), reverse(id, id + n);
    memset(st, 0, sizeof(st));
    s = n - s - 1;
    L = 0, R = -1;
    rek(s, n - 1, 0, s);
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7108 KB Output is correct
2 Correct 65 ms 7092 KB Output is correct
3 Correct 63 ms 7076 KB Output is correct
4 Correct 72 ms 7108 KB Output is correct
5 Correct 83 ms 7072 KB Output is correct
6 Correct 27 ms 6348 KB Output is correct
7 Correct 47 ms 6600 KB Output is correct
8 Correct 55 ms 6600 KB Output is correct
9 Correct 22 ms 6348 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5964 KB Output is correct
2 Correct 7 ms 5964 KB Output is correct
3 Correct 6 ms 5968 KB Output is correct
4 Correct 13 ms 5964 KB Output is correct
5 Correct 11 ms 5964 KB Output is correct
6 Correct 6 ms 5888 KB Output is correct
7 Correct 6 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7052 KB Output is correct
2 Correct 73 ms 7100 KB Output is correct
3 Correct 127 ms 6600 KB Output is correct
4 Correct 9 ms 5964 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 6 ms 5964 KB Output is correct
7 Correct 6 ms 5964 KB Output is correct
8 Correct 465 ms 7832 KB Output is correct
9 Correct 358 ms 7868 KB Output is correct