Submission #1160495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160495		SmuggingSpun	Nile (IOI24_nile)	C++20	100 / 100	244 ms	13356 KiB

nile

#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
const int INF = 1e9;
vector<ll>calculate_costs(vector<int>W, vector<int>A, vector<int>B, vector<int>E){
    int n = W.size(), q = E.size();
    if(n == 1){
        return vector<ll>(q, ll(A[0]));
    }
    if(q <= 5 && n <= 2000 && *max_element(W.begin(), W.end()) == 1){
        ll ans = accumulate(B.begin(), B.end(), 0LL);
        if(n & 1){
            int d = INF;
            for(int i = 0; i < n; i++){
                minimize(d, A[i] - B[i]);
            }
            ans += d;
        }
        return vector<ll>(q, ans);
    } 
    vector<int>p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&] (int i, int j){
        return W[i] < W[j];
    });
    vector<int>pd(n - 1);
    iota(pd.begin(), pd.end(), 0);
    sort(pd.begin(), pd.end(), [&] (int i, int j){
        return W[p[i + 1]] - W[p[i]] < W[p[j + 1]] - W[p[j]];
    });
    vector<int>pst(n - 2);
    iota(pst.begin(), pst.end(), 1);
    sort(pst.begin(), pst.end(), [&] (int i, int j){
        return W[p[i + 1]] - W[p[i - 1]] < W[p[j + 1]] - W[p[j - 1]];
    });
    vector<vector<int>>st(4, vector<int>(n << 2, INF));
    function<void(int, int, int, int, int, int)>update;
    update = [&] (int type, int id, int l, int r, int p, int x){
        if(l == r){
            st[type][id] = x;
            return;
        }
        int m = (l + r) >> 1;
        if(m < p){
            update(type, id << 1 | 1, m + 1, r, p, x);
        }
        else{
            update(type, id << 1, l, m, p, x);
        }
        st[type][id] = min(st[type][id << 1], st[type][id << 1 | 1]);
    };
    function<int(int, int, int, int, int, int)>get;
    get = [&] (int type, int id, int l, int r, int u, int v){
        if(l > v || r < u){
            return INF;
        }
        if(u <= l && v >= r){
            return st[type][id];
        }
        int m = (l + r) >> 1;
        return min(get(type, id << 1, l, m, u, v), get(type, id << 1 | 1, m + 1, r, u, v));
    };
    for(int i = 0; i < n; i++){
        update(i & 1, 1, 0, n - 1, i, A[p[i]] - B[p[i]]);
    }
    auto get_range = [&] (int l, int r){
        return ((r - l) & 1) ? 0 : min(get(l & 1, 1, 0, n - 1, l, r), get(((l & 1) ^ 1) | 2, 1, 0, n - 1, l, r));
    };
    ll cur = accumulate(A.begin(), A.end(), 0LL);
    vector<int>lab(n), l(n), r(n);
    for(int i = 0; i < n; i++){
        lab[i] = l[i] = r[i] = i;
    }
    auto find_set = [&] (int N){
        while(N != lab[N]){
            N = lab[N] = lab[lab[N]];
        }
        return N;
    };
    auto merge = [&] (int u, int v){
        cur -= get_range(l[u = find_set(u)], r[u]) + get_range(l[v = find_set(v)], r[v]);
        minimize(l[lab[v] = u], l[v]);
        maximize(r[u], r[v]);
        cur += get_range(l[u], r[u]);
    };
    vector<int>pq(q);
    iota(pq.begin(), pq.end(), 0);
    sort(pq.begin(), pq.end(), [&] (int i, int j){
        return E[i] < E[j];
    });
    vector<ll>ans(q);
    int ipd = 0, ist = 0;
    for(int& iq : pq){
        while(ist + 2 < n && W[p[pst[ist] + 1]] - W[p[pst[ist] - 1]] <= E[iq]){
            int i = find_set(pst[ist]);
            cur -= get_range(l[i], r[i]);
            update((pst[ist] & 1) | 2, 1, 0, n - 1, pst[ist], A[p[pst[ist]]] - B[p[pst[ist]]]);
            cur += get_range(l[i], r[i]);
            ist++;
        }
        while(ipd + 1 < n && W[p[pd[ipd] + 1]] - W[p[pd[ipd]]] <= E[iq]){
            merge(pd[ipd], pd[ipd] + 1);
            ipd++;
        }
        ans[iq] = cur;
    }
    return ans;
}

• 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