Submission #1317325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317325		spetr	Nile (IOI24_nile)	C++20	0 / 100	55 ms	25812 KiB

nile

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

void buildls(ll l, ll r, ll i, vl& tree, ll p, vl& vals){
    if (l == r && l < vals.size() && l%2 == p){
        tree[i] = vals[l];
        return;
    }
    else if (l == r){return;}
    
    ll mid = (l+r)/2;
    buildls(l, mid, 2*i, tree, p, vals);
    buildls(mid +1, r, 2*i+1, tree, p, vals);
    tree[i] = min(tree[2*i], tree[2*i+1]);
    return;
}

void buildg(ll l, ll r, ll i, vl& tree, vl& vals){
    if (l == r && l < vals.size()){
        tree[i] = vals[l];
        return;
    }

    else if (l == r){return;}

    ll mid = (l+r)/2;
    buildg(l, mid, 2*i, tree, vals);
    buildg(mid +1, r, 2*i+1, tree, vals);
    tree[i] = min(tree[2*i], tree[2*i+1]);
    return;
}

void update(ll l, ll r, vl& tree, ll i, ll c, ll pos){
    if (l == r && l == pos){
        tree[i] = c;
        return;
    }
    if (r < pos || l > pos){
        return;
    }

    ll mid = (l+r)/2;
    update(l, mid, tree, 2*i, c, pos);
    update(mid+1,r,tree,2*i+1, c, pos);
    tree[i] = min(tree[2*i], tree[2*i+1]);
    return;
}

ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){
    if (L <= l && r <= R){
        return tree[i];
    }
    if (r < L || R < l){
        return 1e10;
    }

    ll mid = (l+r)/2;
    ll a = query(l, mid, L, R, 2*i, tree);
    ll b = query(mid+1, r, L, R, 2*i+1, tree);
    return min(a,b);
}

std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A, 
    std::vector<int> B, std::vector<int> E){

    ll n = W.size();
    vll nums;
    for (ll i = 0; i < n; i++){
        nums.push_back({W[i], A[i], B[i]});
    }
    sort(nums.begin(), nums.end());

    vector<pl> queries;
    for (ll i = 0; i < E.size(); i++){
        queries.push_back({E[i], i});
    }
    sort(queries.begin(), queries.end());
    reverse(queries.begin(), queries.end());

    // Intervals
    set<ll> b;
    b.insert(0);
    vector<pl> intervals (n, {-1,0});

    // Events
    vector<pl> gaps;
    for (ll i = 0; i < n-1; i++){
        gaps.push_back({nums[i+1][0]-nums[i][0], i});
    }
    sort(gaps.begin(), gaps.end()); reverse(gaps.begin(), gaps.end()); gaps.push_back({-1,0});

    vector<pl> spojky;
    for (ll i = 1; i < n-1; i++){
        spojky.push_back({nums[i+1][0]-nums[i-1][0], i});
    }
    sort(spojky.begin(), spojky.end());  reverse(spojky.begin(), spojky.end()); spojky.push_back({-1,0});

    // Precalc
    vl dif(n);
    for (ll i = 0; i < n; i++){dif[i] = nums[i][1]-nums[i][2];}

    // Tree handeling
    vl treel (4*n+4, 1e10);
    vl trees (4*n + 4, 1e10);
    vl treeg (4*n+4, 1e10);
    ll N = 1;
    while (N < n){ N *= 2;}
    buildls(0,N-1,1,treel,1, dif);//parity
    buildls(0,N-1,1,trees,0, dif);
    buildg(0,N-1,1,treeg, dif);

    vl prefix (n+1,0);
    for (ll i = 0; i < n; i++){
        prefix[i+1] = prefix[i] + nums[i][2];
    }

    ll suma = prefix[n] - prefix[0] + query(0,N-1,0,n-1,1,treeg); // (i, j) = [j+1] - [i]
    intervals[0] = {n-1, suma};

    vl ans(queries.size(), 0);

    // interval calc
    auto intcalc = [&](ll zacatek, ll konec) {
        ll sub = prefix[konec+1]-prefix[zacatek];

        if ((konec - zacatek)%2 == 0){ // odd length is a problem, but bounds are including 
            return konec-zacatek+2;
        }
        return konec-zacatek+1;
    };

    // main algorithm
    ll p1 = 0; ll p2 = 0;

    for (ll i = 0; i < queries.size(); i++){
        // Handle updates of spojky deleting, interval destruction, by gaps
        ll k = queries[i].first;
        while (gaps[p2].first > k){
            
                ll end1 = gaps[p2].second; //position of last element of first interval
                ll start1 = *prev(b.upper_bound(end1));
                ll end2 = intervals[start1].first;
                ll start2 = end1 + 1;
                suma -= intervals[start1].second;

                ll sub = intcalc(start1, end1);
                intervals[start1] = {end1, sub};
                suma += sub;

                sub = intcalc(start2, end2);
                intervals[start2] = {end2, sub};
                b.insert(start2);
                suma += sub;
                
                p2++;
            
        }
        ans[queries[i].second] = suma;
    }

    return ans;
}

/*/int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> W, A, B, E;
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++){
        ll a,b,c;
        cin >>a >> b >> c;
        W.push_back(a);
        A.push_back(b);
        B.push_back(c);
    }
    ll q;
    cin >> q;
    for (ll i = 0; i < q; i++){
        ll a;
        cin >> a;
        E.push_back(a);
    }

    
    vl x = calculate_costs(W, A, B, E);
    for (auto p : x){
        cout << p << "\n";
}   
    return 0;
}/*/

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