oj.uz

Submission #856582

# Submission time Handle Problem Language Result Execution time Memory
856582 2023-10-04T02:27:22 Z fanwen Holiday (IOI14_holiday) C++17
100 / 100
 161 ms 44364 KB 
#include <bits/stdc++.h>

#include "holiday.h"

using namespace std;

const int MAXN = 1e5 + 5;

int n, d, start, a[MAXN], root[MAXN];

long long ans = 0;
vector <int> cmp;

struct node_t {
    int le, ri, cnt = 0;
    long long sum = 0;
} it[18 * MAXN];

int Time;

void update(int pre, int nxt, int l, int r, int u, int val) {

    if(l > u || r < u || l > r) return;
    if(l == r) {
        it[nxt].sum = it[pre].sum + 1LL * val * cmp[l - 1];
        it[nxt].cnt = it[pre].cnt + val;
        return;
    }

    int mid = l + r >> 1;

    if(u <= mid) {
        it[nxt].ri = it[pre].ri;
        it[nxt].le = ++Time;
        update(it[pre].le, it[nxt].le, l, mid, u, val);
    } else {
        it[nxt].le = it[pre].le;
        it[nxt].ri = ++Time;
        update(it[pre].ri, it[nxt].ri, mid + 1, r, u, val);
    }

    it[nxt].cnt = it[it[nxt].le].cnt + it[it[nxt].ri].cnt;
    it[nxt].sum = it[it[nxt].le].sum + it[it[nxt].ri].sum;
}

long long getMax(int pre, int nxt, int l, int r, int cnt) {
    if(cnt <= 0) return 0;
    if(l == r) return 1LL * cnt * cmp[l - 1];

    int mid = l + r >> 1;

    int tmp = it[it[nxt].ri].cnt - it[it[pre].ri].cnt; 
    if(cnt <= tmp) return getMax(it[pre].ri, it[nxt].ri, mid + 1, r, cnt);
    long long ans = it[it[nxt].ri].sum - it[it[pre].ri].sum;
    ans += getMax(it[pre].le, it[nxt].le, l, mid, cnt - tmp);
    return ans;
}

void divide_and_conquer(int l, int r, int u, int v) {
    if(l > r) return;
    int mid = l + r >> 1;
    long long cost = -1;
    int p = u;
    for (int i = u; i <= v; ++i) {
        int L = start - mid, R = i - start, cnt = d - L - R - min(L, R);
        cnt = min(cnt, i - mid + 1);
        if(cnt < 0) continue;
        long long tmp = getMax(root[mid - 1], root[i], 1, n, cnt);
        if(cost < tmp) {
            cost = tmp;
            p = i;
        }
    }
    ans = max(ans, cost);
    divide_and_conquer(l, mid - 1, u, p);
    divide_and_conquer(mid + 1, r, p, v);
}

long long findMaxAttraction(int _n, int _start, int _d, int A[]) {
    ans = Time = 0;
    n = _n, d = _d, start = _start + 1;
    for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
    cmp = vector <int> (a + 1, a + n + 1);
    sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
    }
    // for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];

    for (int i = 1; i <= n; ++i) {
        root[i] = ++Time;
        update(root[i - 1], root[i], 1, n, a[i], 1);
    }

    divide_and_conquer(1, start, start, n);
    return ans;
}
 
#ifdef LOCAL
 
#include<cstdio>
 
int main() {
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
        n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}
 
#endif // LOCAL
 
// Dream it. Wish it. Do it.

Compilation message

holiday.cpp: In function 'void update(int, int, int, int, int, int)':
holiday.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int getMax(int, int, int, int, int)':
holiday.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void divide_and_conquer(int, int, int, int)':
holiday.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44120 KB Output is correct
2 Correct 31 ms 44120 KB Output is correct
3 Correct 31 ms 44120 KB Output is correct
4 Correct 31 ms 44124 KB Output is correct
5 Correct 35 ms 44112 KB Output is correct
6 Correct 15 ms 43356 KB Output is correct
7 Correct 26 ms 43516 KB Output is correct
8 Correct 25 ms 43612 KB Output is correct
9 Correct 13 ms 43100 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43100 KB Output is correct
2 Correct 6 ms 42924 KB Output is correct
3 Correct 7 ms 43100 KB Output is correct
4 Correct 8 ms 43136 KB Output is correct
5 Correct 7 ms 42892 KB Output is correct
6 Correct 7 ms 43100 KB Output is correct
7 Correct 6 ms 43100 KB Output is correct
8 Correct 7 ms 43100 KB Output is correct
9 Correct 6 ms 43096 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 44204 KB Output is correct
2 Correct 45 ms 44364 KB Output is correct
3 Correct 41 ms 43612 KB Output is correct
4 Correct 8 ms 42900 KB Output is correct
5 Correct 7 ms 42912 KB Output is correct
6 Correct 7 ms 43100 KB Output is correct
7 Correct 7 ms 43100 KB Output is correct
8 Correct 161 ms 44128 KB Output is correct
9 Correct 151 ms 44116 KB Output is correct