제출 #1160477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160477		SmuggingSpun	나일강 (IOI24_nile)	C++20	38 / 100	94 ms	8260 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(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>st(n << 2, INF);
    function<void(int, int, int)>build;
    build = [&] (int id, int l, int r){
        if(l == r){
            st[id] = A[p[l]] - B[p[l]];
            return;
        }
        int m = (l + r) >> 1;
        build(id << 1, l, m);
        build(id << 1 | 1, m + 1, r);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    };
    build(1, 0, n - 1);
    function<int(int, int, int, int, int)>get;
    get = [&] (int id, int l, int r, int u, int v){
        if(l > v || r < u){
            return INF;
        }
        if(u <= l && v >= r){
            return st[id];
        }
        int m = (l + r) >> 1;
        return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    };
    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){
        if(~(r[u = find_set(u)] - l[u]) & 1){
            cur -= get(1, 0, n - 1, l[u], r[u]);
        }
        if(~(r[v = find_set(v)] - l[v]) & 1){
            cur -= get(1, 0, n - 1, l[v], r[v]);
        }
        minimize(l[lab[v] = u], l[v]);
        maximize(r[u], r[v]);
        if(~(r[u] - l[u]) & 1){
            cur += get(1, 0, n - 1, 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;
    for(int& iq : pq){
        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: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18