oj.uz

Submission #795556

# Submission time Handle Problem Language Result Execution time Memory
795556 2023-07-27T11:16:38 Z phoebe Holiday (IOI14_holiday) C++17
100 / 100
 1183 ms 5480 KB 
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
#define ALL(x) x.begin(), x.end()
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 1e5 + 10;
int n, s, d, a[maxn], cnt[maxn * 4] = {0}, cur_l = 0, cur_r = 0;
ll tree[maxn * 4] = {0}, re = 0;
vector<int> pt;

int get(int v){
    return lower_bound(ALL(pt), v) - pt.begin();
}

int calc_dist(int l, int r){
    if (l >= s) return r - s;
    if (r <= s) return s - l;
    return r - l + min(r - s, s - l);
}

void update(int x, int delta, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        tree[i] += pt[x] * delta, cnt[i] += delta; 
        return;
    }
    int tm = (tl + tr) / 2;
    update(x, delta, tl, tm, i * 2); 
    update(x, delta, tm + 1, tr, i * 2 + 1);
    tree[i] = tree[i * 2] + tree[i * 2 + 1];
    cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
}

pair<ll, int> walk(int rem, int tl = 0, int tr = maxn, int i = 1){
    // sum, cnt
    if (rem <= 0) return {0, 0};
    if (cnt[i] <= rem) return {tree[i], cnt[i]};
    if (tl == tr) return {pt[tl] * rem, rem};
    int tm = (tl + tr) / 2;
    auto right = walk(rem, tm + 1, tr, i * 2 + 1);
    auto left = walk(rem - right.S, tl, tm, i * 2);
    return {left.F + right.F, left.S + right.S};
}

ll cost(int l, int r, int rem){
    while (cur_l > l) update(get(a[--cur_l]), 1);
    while (cur_r < r) update(get(a[++cur_r]), 1);
    while (cur_l < l) update(get(a[cur_l++]), -1);
    while (cur_r > r) update(get(a[cur_r--]), -1);
    // cout << l << ' ' << r << ' ' << walk(rem).F << ' ' << walk(rem).S << ' ' << rem << endl;
    return walk(rem).F;
}

void solve(int l, int r, int opt_l, int opt_r){
    if (l > r) return;
    int r_pos = (l + r) / 2; // right end point
    ll best = 0; int opt;
    for (int l_pos = opt_l; l_pos <= min(r_pos, opt_r); l_pos++){ 
        ll val = cost(l_pos, r_pos, d - calc_dist(l_pos, r_pos));
        if (val > best) best = val, opt = l_pos;
    }
    // cout << opt << ' ' << r_pos << ' ' << best << endl;
    re = max(re, best); 
    solve(l, r_pos - 1, opt_l, opt);
    solve(r_pos + 1, r, opt, opt_r);
}

ll findMaxAttraction(int N, int start, int D, int attraction[]){
    n = N, s = start, d = D;
    for (int i = 0; i < n; i++){
        a[i] = attraction[i];
        pt.PB(a[i]);
    }
    sort(ALL(pt)); pt.resize(distance(pt.begin(), unique(ALL(pt))));
    update(get(a[0]), 1); 
    // for (auto x : tree[1]) cout << x << ' '; cout << endl;
    solve(0, n - 1, 0, n - 1);
    return re;
}

Compilation message

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:73:10: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     solve(l, r_pos - 1, opt_l, opt);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 1868 KB Output is correct
2 Correct 35 ms 1868 KB Output is correct
3 Correct 363 ms 1868 KB Output is correct
4 Correct 369 ms 1868 KB Output is correct
5 Correct 499 ms 1860 KB Output is correct
6 Correct 117 ms 1108 KB Output is correct
7 Correct 245 ms 1364 KB Output is correct
8 Correct 319 ms 1488 KB Output is correct
9 Correct 83 ms 1108 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 944 KB Output is correct
2 Correct 8 ms 852 KB Output is correct
3 Correct 12 ms 852 KB Output is correct
4 Correct 17 ms 836 KB Output is correct
5 Correct 14 ms 916 KB Output is correct
6 Correct 5 ms 704 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 2508 KB Output is correct
2 Correct 586 ms 5480 KB Output is correct
3 Correct 259 ms 3024 KB Output is correct
4 Correct 14 ms 840 KB Output is correct
5 Correct 5 ms 696 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 1121 ms 5120 KB Output is correct
9 Correct 1183 ms 5196 KB Output is correct