Submission #1221378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221378		golomb	Nile (IOI24_nile)	C++20	100 / 100	132 ms	17840 KiB

nile

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> calculate_costs( vector<int> W, vector<int> A, vector<int> B, vector<int> Q ){
    int n = W.size();
    int q = Q.size();

    vector<int> inds(n);
    iota(inds.begin(),inds.end(),0);
    sort(inds.begin(),inds.end(),[&](int a,int b){
        return W[a] < W[b];
    });
    vector<ll> weights(n), penalty(n);
    for( int i = 0; i < n; i++ ){
        weights[i] = W[inds[i]];
        penalty[i] = A[inds[i]] - B[inds[i]];
    }

    vector<pair<ll,int>> events;
    events.push_back( {LLONG_MAX,-1} );
    for( int i = 0; i < n-1; i++ )
        events.push_back( {weights[i+1]-weights[i],2*i} );
    for( int i = 0; i < n-2; i++ )
        events.push_back( {weights[i+2]-weights[i],2*i+1} );
    sort(events.rbegin(),events.rend());

    vector<ll> output(q);
    inds.resize(q);
    iota(inds.begin(),inds.end(),0);
    sort(inds.begin(),inds.end(),[&](int a,int b){
        return Q[a] < Q[b];
    });

    ll ans = 0;
    for( auto e: A ) ans += e;
    set<int> bounds;
    for( int i = 0; i <= n; i++ ) bounds.insert(i);
    vector<ll> segpenalty = penalty;
    vector<ll> mineven(n,LLONG_MAX);
    vector<ll> minodd(n,LLONG_MAX);
    vector<ll> togeven(n,LLONG_MAX);
    vector<ll> togodd(n,LLONG_MAX);
    for( int i = 0; i < n; i++ ){
        if( i%2 == 0 ) mineven[i] = penalty[i];
        else minodd[i] = penalty[i];
    }

    for( int i = 0; i < q; i++ ){
        ll query = Q[inds[i]];
        while( events.back().first <= query ){
            int ev = events.back().second; events.pop_back();
            int x = ev/2;
            if( ev%2 == 0 ){
                auto it = bounds.upper_bound(x);
                int L = *prev(it), M = *it, R = *next(it);
                bounds.erase(M);

                ans -= segpenalty[L];
                ans -= segpenalty[M];
                mineven[L] = min(mineven[L],mineven[M]);
                minodd[L] = min(minodd[L],minodd[M]);
                togeven[L] = min(togeven[L],togeven[M]);
                togodd[L] = min(togodd[L],togodd[M]);

                if( (R-L)%2 == 0 ){
                    segpenalty[L] = 0;
                } else {
                    if( L%2 == 0 ) segpenalty[L] = min(mineven[L],togodd[L]);
                    else segpenalty[L] = min(minodd[L],togeven[L]);
                }
                ans += segpenalty[L];
            } else {
                auto it = bounds.upper_bound(x);
                int L = *prev(it), R = *it;
                ans -= segpenalty[L];
                if( (x+1)%2 == 0 ) togeven[L] = min(togeven[L], penalty[x+1]);
                else togodd[L] = min(togodd[L], penalty[x+1]);

                if( (R-L)%2 == 0 ){
                    segpenalty[L] = 0;
                } else {
                    if( L%2 == 0 ) segpenalty[L] = min(mineven[L],togodd[L]);
                    else segpenalty[L] = min(minodd[L],togeven[L]);
                }
                ans += segpenalty[L];
            }
        }
        output[inds[i]] = ans;
    }
    return output;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18