Submission #1210468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210468		PagodePaiva	Nile (IOI24_nile)	C++20	100 / 100	218 ms	24440 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#define c custo

using namespace std;

const int N = 200010;
long long dp[N];
long long custo[N];
long long w[N];
long long pref[N];
int n;

struct Segtree{
    long long tree[4*N];
    long long join(long long a, long long b){
        return min(a, b);
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = 1e18;
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(int node, int l, int r, int pos, long long val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l+r)/2;
        if(l <=  pos and pos <= mid)
            update(2*node, l, mid, pos, val);
        else
            update(2*node+1, mid+1, r, pos, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    long long query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r)
            return 1e18;
        if(l <= tl and tr <= r)
            return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg[3];

long long resposta_query[N];

long long calcular_resposta(int l, int r){
    long long soma = pref[r] - pref[l-1];
    int tam = r-l+1;
    ////cout << soma << '\n';
    if(tam%2 == 0)
        return soma;
    long long mn = 1e18;
    if(l%2 == 0){
        mn = seg[1].query(1, l, r, 1, n);
    }
    else{
        mn = seg[0].query(1, l, r, 1, n);
    }
    mn = min(mn, seg[2].query(1, l, r, 1, n));
    ////cout << mn << '\n';
    return soma - mn;
}

vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
    n = W.size();
    long long sum = 0;
    vector <array <int, 3>> ordenar;
    for(int i = 0;i < n;i++){
        ordenar.push_back({W[i], A[i], B[i]});
    }
    vector <pair <int, int>> query;
    for(int i = 0;i < E.size();i++){
        query.push_back({E[i], i});
    }
    sort(query.begin(), query.end());
    sort(ordenar.begin(), ordenar.end());
    for(int i = 0;i < n;i++){
        w[i+1] = ordenar[i][0];
        sum += (long long) (ordenar[i][1]);
        custo[i+1] = ordenar[i][1] - ordenar[i][2];
        pref[i+1] = pref[i] + custo[i+1];
    }
    vector <long long> resposta;
    vector <array <long long, 3>> updates;
    for(int i = 2;i <= n;i++){
        updates.push_back({w[i]-w[i-1], i-1, i});
        if(i != n){
            updates.push_back({w[i+1]-w[i-1], i-1, i+1});
        }
    }
    seg[0].build(1, 1, n);
    seg[1].build(1, 1, n);
    seg[2].build(1, 1, n);
    for(int i = 1;i <= n;i += 2){
        seg[0].update(1, 1, n, i, custo[i]);
    }
    for(int i = 2;i <= n;i += 2){
        seg[1].update(1, 1, n, i, custo[i]);
    }
    sort(updates.begin(), updates.end());
    int ponteiro = 0;
    long long ans = 0;
    set <pair <int, int>> intervalos;
    for(int i = 1;i <= n;i++){
        intervalos.insert({i, i});
    }
    for(auto [d, p1, p2] : updates){
        //cout << d << ' ' << ans << '\n';
        while(ponteiro < query.size()){
            if(d > query[ponteiro].first){
                resposta_query[query[ponteiro].second] = sum-ans;
                ponteiro++;
            }
            else
                break;
        }
        if(p1 == p2-1){
            auto it = intervalos.lower_bound({p2, 0});
            auto [l2, r2] = *it;
            it--;
            auto [l1, r1] = *it;
            if(d == 2){
                //cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
            }
            ans -= calcular_resposta(l1, r1);
            ans -= calcular_resposta(l2, r2);
            intervalos.erase({l1, r1});
            intervalos.erase({l2, r2});
            ans += calcular_resposta(l1, r2);
            intervalos.insert({l1, r2});
        }
        else{
            int pos = p1+1;
            auto it = intervalos.lower_bound({pos, 0});
            it--;
            auto [l, r] = *it;
            ans -= calcular_resposta(l, r);
            seg[2].update(1, 1, n, pos, custo[pos]);
            ans += calcular_resposta(l, r);
        }
    }
    while(ponteiro < query.size()){
        if(true){
            resposta_query[query[ponteiro].second] = sum-ans;
            ponteiro++;
        }
        else
            break;
    }
    for(int i = 0;i < E.size();i++)
        resposta.push_back(resposta_query[i]);
    return resposta;
}

• 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