제출 #1244167

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

nile

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

#define SZ(x) int(x.size())

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second

template<typename T> void permute(vector<T> &A, vector<int> &p) {
    vector<T> B(SZ(A));
    for(int i=0; i<SZ(A); i++)
        B[i] = A[p[i]];
    A = B;
}

const int MXN = 1e5+5;

int n, q;
vector<int> ord, ordq;

int dsu[MXN], sz[MXN], mnod[MXN], mnev[MXN], val[MXN];
ll ANS;

inline int get(int v) {
    return (sz[v]&1) ? min(mnod[v], val[v]) : 0;
}
inline void init(vector<int> &A, vector<int> &B) {
    ANS = 0;
    for(int i=0; i<n; i++) {
        dsu[i] = i;
        sz[i] = 1;
        mnod[i] = A[i]-B[i];
        mnev[i] = 1e9;
        val[i] = 1e9;
        ANS += get(i);
    }
}
int find(int v) { return v==dsu[v] ? v : dsu[v]=find(dsu[v]); }
inline void merge(int u, int v) {
    u = find(u);
    v = find(v);
    assert(u!=v);
    ANS -= get(u);
    ANS -= get(v);
    mnod[u] = min(mnod[u], (sz[u]&1) ? mnev[v] : mnod[v]);
    mnev[u] = min(mnev[u], (sz[u]&1) ? mnod[v] : mnev[v]);
    val[u] = min(val[u], val[v]);
    sz[dsu[v]=u] += sz[v];
    ANS += get(u);
}
inline void add(int i, int x) {
    i = find(i);
    ANS -= get(i);
    val[i] = min(val[i], x);
    ANS += get(i);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    n = SZ(W), q = SZ(E);
    ord.resize(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return W[i]<W[j];
    });
    permute(W, ord);
    permute(A, ord);
    permute(B, ord);
    ordq.resize(q);
    iota(ordq.begin(), ordq.end(), 0);
    sort(ordq.begin(), ordq.end(), [&](int i, int j) {
        return E[i]<E[j];
    });
    permute(E, ordq);
    vector<pii> v1, v2;
    for(int i=0; i+1<n; i++) {
        v1.push_back({W[i+1]-W[i], i});
        if(i+2<n) v2.push_back({W[i+2]-W[i], i});
    }
    sort(v1.begin(), v1.end()); reverse(v1.begin(), v1.end());
    sort(v2.begin(), v2.end()); reverse(v2.begin(), v2.end());
    init(A, B);
    vector<ll> ans(q);
    ll sumb=0;
    for(int i : B) sumb += i;
    for(int i=0; i<q; i++) {
        while(!v1.empty() && v1.back().X<=E[i]) {
            merge(v1.back().Y, v1.back().Y+1);
            v1.pop_back();
        }
        while(!v2.empty() && v2.back().X<=E[i]) {
            add(v2.back().Y+1, A[v2.back().Y+1]-B[v2.back().Y+1]);
            v2.pop_back();
        }
        ans[ordq[i]] = sumb + ANS;
    }
    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