제출 #1131923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131923		garam1732	나일강 (IOI24_nile)	C++20	100 / 100	114 ms	14272 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 2e18;

int par[MAXN];
ll sum[MAXN], cnt[MAXN];
ll odd[MAXN], even[MAXN], mn[MAXN];

int root(int x) { return par[x]==x?x:par[x]=root(par[x]); }
vector<pi> v, w, qry;
vector<ll> res;

struct Artifact {
    ll w,a,b;
}arr[MAXN];

ll f(int x) {
    ll t = sum[x];
    if(cnt[x]&1) t -= min(mn[x], odd[x]);
    return t;
}

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

    int n = W.size();
    for(int i=0; i<n; i++) par[i] = i;

    for(int i=0; i<n; i++) arr[i] = {W[i], A[i], B[i]};
    sort(arr, arr+n, [&](Artifact &a, Artifact &b) { return a.w < b.w; });

    for(int i=1; i<n; i++) v.push_back(pi(arr[i].w-arr[i-1].w, i));
    for(int i=1; i<n-1; i++) w.push_back(pi(arr[i+1].w-arr[i-1].w, i));
    sort(all(v)); sort(all(w));

    int q=E.size();
    for(int i=0; i<q; i++) qry.push_back(pi(E[i], i));
    sort(all(qry));

    ll t = 0;
    for(int x:A) t+=x;
    for(int i=0; i<n; i++) sum[i] = odd[i] = arr[i].a-arr[i].b, cnt[i]=1, mn[i]=even[i]=INT_MAX;

    res.resize(q);
    for(int i=0, j=0, k=0; j<q; j++) {
        while(k<w.size() && w[k].ff <= qry[j].ff) {
            int x = root(w[k].ss);
            t += f(x);
            mn[x] = min(mn[x], arr[w[k].ss].a-arr[w[k].ss].b);
            t -= f(x);
            k++;
        }

        while(i<v.size() && v[i].ff <= qry[j].ff) {
            int x = root(v[i].ss-1);

            t += f(x); t += f(v[i].ss);

            if(cnt[x]&1) {
                odd[x] = min(odd[x], even[v[i].ss]);
                even[x] = min(even[x], odd[v[i].ss]);
            } else {
                odd[x] = min(odd[x], odd[v[i].ss]);
                even[x] = min(even[x], even[v[i].ss]);
            }
            mn[x] = min(mn[x], mn[v[i].ss]);
            sum[x] += sum[v[i].ss];
            cnt[x] += cnt[v[i].ss];
            par[v[i].ss] = x;

            t -= f(x);

            i++;
        }

        res[qry[j].ss] = t;
    }

    return res;
}

• 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