oj.uz

Submission #905521

# Submission time Handle Problem Language Result Execution time Memory
905521 2024-01-13T03:11:56 Z pemguimn Holiday (IOI14_holiday) C++14
100 / 100
 239 ms 51972 KB 
#include "holiday.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 3e5 + 5, INF = 2e9;

int n, d, start, a[N], ori[N], sz; long long ans = -INF;
vector<int> val;
struct node{
    int cnt, l, r; long long sum;
    node(){
        l = r = cnt = sum = 0;
    }
};

vector<node> nodes;

int root[N];

int build(int l, int r){
    int id = nodes.size();
    nodes.push_back(node());
    if(l == r){
        return id;
    }
    int mid = (l + r) / 2;
    nodes[id].l = build(l, mid);
    nodes[id].r = build(mid + 1, r);
    return id;
}

int upd(int k, int tl, int tr, int i, int x){
    int id = nodes.size();
    nodes.push_back(node());
    if(tl == tr){
        nodes[id].cnt = nodes[k].cnt + 1;
        nodes[id].sum = nodes[k].sum + ori[tl];
        return id;
    }

    int mid = (tl + tr) / 2;
    if(i <= mid){
        nodes[id].l = upd(nodes[k].l, tl, mid, i, x);
        nodes[id].r = nodes[k].r;
    } else{
        nodes[id].l = nodes[k].l;
        nodes[id].r = upd(nodes[k].r, mid + 1, tr, i, x);
    }
    nodes[id].cnt = nodes[nodes[id].l].cnt + nodes[nodes[id].r].cnt;
    nodes[id].sum = nodes[nodes[id].l].sum + nodes[nodes[id].r].sum;
    return id;
}

long long query(int l, int r, int tl, int tr, int k){
    if(tl == tr){
        return 1LL * ori[tl] * min(k, nodes[r].cnt - nodes[l].cnt);
    }

    int mid = (tl + tr) / 2; 

    if(nodes[nodes[r].r].cnt - nodes[nodes[l].r].cnt >= k){
        return query(nodes[l].r, nodes[r].r, mid + 1, tr, k);
    } else{
//        cout << ori[mid + 1] << " " << r -> r -> cnt - l -> r -> cnt << " " << r -> r -> sum - l -> r -> sum << endl;
        return nodes[nodes[r].r].sum - nodes[nodes[l].r].sum + query(nodes[l].l, nodes[r].l, tl, mid, k - (nodes[nodes[r].r].cnt - nodes[nodes[l].r].cnt));
    }
}
long long cost(int l, int start, int r){
    int queryop = min(d - (r - l + min(r - start, start - l)), r - l + 1);
    if(queryop < 0) return -INF;
//    cout << l << ' ' << start << " " << r << ' ' << queryop << " " << query(root[l - 1], root[r], 0, sz, queryop)<< endl;
    return query(root[l - 1], root[r], 0, sz, queryop);
}
void dnc(int l, int r, int optl, int optr){
    if(l > r) return;
    int mid = (l + r) / 2;
    pair<long long, int> best = {-INF, 0};
    for(int i = optl; i <= min(optr, mid); i++){
        best = max(best, {cost(i, start, mid), i});
    }
    ans = max(ans, best.first);
    dnc(l, mid - 1, optl, best.second);
    dnc(mid + 1, r, best.second, optr);
}

long long int findMaxAttraction(int nn, int startt, int dd, int attraction[]){
    n = nn, start = startt, d = dd;
    start++;
    for(int i = 0; i < n; i++){
        a[i + 1] = attraction[i];
    }
    for(int i = 1; i <= n; i++) val.push_back(a[i]);
    sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin());
    for(int i = 0; i < (int) val.size(); i++) ori[i] = val[i];
    sz = val.size() - 1;
    nodes.reserve(40e6);
    root[0] = build(0, sz);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
        root[i] = upd(root[i - 1], 0, sz, a[i], 1);
    }
    dnc(start, n, 1, start);
    return ans;
}

// int main() {
//     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;
// }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3064 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 2 ms 2808 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 3056 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7008 KB Output is correct
2 Correct 17 ms 6612 KB Output is correct
3 Correct 15 ms 9936 KB Output is correct
4 Correct 16 ms 9936 KB Output is correct
5 Correct 42 ms 21704 KB Output is correct
6 Correct 13 ms 8284 KB Output is correct
7 Correct 25 ms 14552 KB Output is correct
8 Correct 26 ms 15828 KB Output is correct
9 Correct 8 ms 8536 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3928 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 4 ms 3676 KB Output is correct
5 Correct 4 ms 3672 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 2904 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6480 KB Output is correct
2 Correct 85 ms 51096 KB Output is correct
3 Correct 52 ms 23724 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 3 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 225 ms 51972 KB Output is correct
9 Correct 239 ms 51840 KB Output is correct