oj.uz

Submission #882913

# Submission time Handle Problem Language Result Execution time Memory
882913 2023-12-04T06:34:04 Z ND0322 Holiday (IOI14_holiday) C++17
100 / 100
 524 ms 10384 KB 
#include <bits/stdc++.h>
#include <iostream>

using namespace std;



const int MAXN = 1e5+5;

long long  N, n, start, d, tmp[MAXN],  b[MAXN], stp[MAXN<<2], stc[MAXN<<2], ans;

int lo, hi;


//first is pos
//second is cost

vector<long long> a;

void updatep(int node, int l, int r, int i, int val){
    if(l == r){
        stp[node] += val;
        return;
    }

    int mid = (l+r)>>1;

    if(i <= mid) updatep(node<<1, l, mid, i, val);
    else updatep(node<<1|1, mid+1, r, i, val);
    stp[node] = stp[node<<1] + stp[node<<1|1];
}

void updatec(int node, int l, int r, int i, long long val){
    if(l == r){
        stc[node] += val;
        return;
    }

    int mid = (l+r)>>1;

    if(i <= mid) updatec(node<<1,l,mid,i,val);
    else updatec(node<<1|1, mid+1, r, i, val);
    stc[node] = stc[node<<1] + stc[node<<1|1];
}

void update(int l, int r){
    while(l < lo){
        updatep(1, 1, n, b[lo-1], 1);
        updatec(1, 1, n, b[lo-1], tmp[lo-1]);
        lo--;
    }

    while(l > lo){
        updatep(1, 1, n, b[lo], -1);
        updatec(1, 1, n, b[lo], -tmp[lo]);
        lo++;
    }

    while(r < hi){
        updatep(1, 1, n, b[hi], -1);
        updatec(1, 1, n, b[hi], -tmp[hi]);
        hi--;
    }

    while(r > hi){
        updatep(1, 1, n, b[hi+1], 1);
        updatec(1, 1, n, b[hi+1], tmp[hi+1]);
        hi++;
    }
}

//the query is weird so recursive seg
long long query(int node, int l, int r, int i){
    if(l == r){
        long long c = stc[node];

        //im fkn bald
        if(stp[node] > i) c -= a[l-1] * (long long)(stp[node] - i);
        return c;
    }

    int mid = (l+r)>>1;

    if(stp[node<<1|1] >= i) return query(node<<1|1, mid+1, r, i);
    return stc[node<<1|1] + query(node<<1, l,mid, i - stp[node<<1|1]);
}


void dac(int l, int r, int p1, int p2){
    if(l > r) return;

    int mid = (l+r)>>1;

    int best = -1;
    long long res = -1;

    for(int i = p2; i >= p1; i--){
        update(mid,i);

        long long dist = min(i-start, start - mid) + i - mid;
        if(dist > d) continue;

        long long c = query(1,1,n,d-dist);
        if(c > res){
            res = c;
            best = i;
        }
    }

    ans = max(ans,res);

    if(best == -1){
        dac(mid+1, r, p1, p2);
        return;
    }

    dac(l,mid-1, p1, best);
    dac(mid+1,r,best,p2);


}

long long int findMaxAttraction(int nn, int s, int dd, int attraction[]){
    
    N = nn;
    start = s;
    d = dd;

    start++;

    for(int i = 1; i <= N; i++){
        tmp[i] = attraction[i-1];
        a.push_back(tmp[i]);
    }

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end() ), a.end());

    //for(int i : a) cout << i << "\n";

    n = a.size();

    lo = 1;
    hi = N;

    for(int i = 1; i <= N; i++){
        b[i] = lower_bound(a.begin(), a.end(), tmp[i])-a.begin()+1;
        updatep(1,1,n,b[i],1);
        updatec(1,1,n,b[i], tmp[i]);
    }

    dac(1, start, start, N);
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7376 KB Output is correct
2 Correct 10 ms 7376 KB Output is correct
3 Correct 11 ms 7452 KB Output is correct
4 Correct 12 ms 7540 KB Output is correct
5 Correct 25 ms 7628 KB Output is correct
6 Correct 8 ms 5588 KB Output is correct
7 Correct 14 ms 6100 KB Output is correct
8 Correct 17 ms 6612 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 4 ms 4960 KB Output is correct
4 Correct 8 ms 4952 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4964 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8144 KB Output is correct
2 Correct 49 ms 10384 KB Output is correct
3 Correct 128 ms 8652 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 524 ms 10188 KB Output is correct
9 Correct 496 ms 10256 KB Output is correct