| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1255966 | farhan11679 | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
// Compile: g++ -std=gnu++17 -O2 -pipe -static -s -o nile nile.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;
struct DSU {
int n;
vector<int> p;
vector<int> sz;
// info per component root:
vector<int> minIndex; // minimum index in component
vector<ll> minC_par[2]; // min C for global parity 0/1 inside comp (use vectors of size n but index by root)
vector<ll> minEnabled; // min C among enabled indices in comp (enabled by (i,i+2) pairs)
DSU(int n=0): n(n), p(n), sz(n), minIndex(n), minEnabled(n, INF) {
for(int i=0;i<n;i++){ p[i]=i; sz[i]=1; minIndex[i]=i; minC_par[0].push_back(INF); minC_par[1].push_back(INF); }
// NOTE: we used push_back above; that made the parity arrays length n. We'll access by index.
}
int find(int a){ return p[a]==a ? a : p[a]=find(p[a]); }
// helper to initialize parity minima per node (call before any unions)
void init_parity_min(int idx, ll Cval){
minC_par[0][idx] = minC_par[0][idx]; // already INF
minC_par[1][idx] = minC_par[1][idx];
int par = idx & 1;
minC_par[par][idx] = Cval;
}
// merge b into a (rooted)
void unite_roots(int ra, int rb){
if(ra==rb) return;
if(sz[ra] < sz[rb]) swap(ra, rb);
// rb into ra
p[rb] = ra;
sz[ra] += sz[rb];
// min index
minIndex[ra] = min(minIndex[ra], minIndex[rb]);
// parity mins
minC_par[0][ra] = min(minC_par[0][ra], minC_par[0][rb]);
minC_par[1][ra] = min(minC_par[1][ra], minC_par[1][rb]);
// enabled mins
minEnabled[ra] = min(minEnabled[ra], minEnabled[rb]);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if(!(cin>>N)) return 0;
vector<long long> W(N), A(N), B(N);
for(int i=0;i<N;i++){
cin >> W[i] >> A[i] >> B[i];
}
int Q; cin >> Q;
vector<long long> E(Q);
for(int i=0;i<Q;i++) cin >> E[i];
// Sort by weight, keep mapping
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j){ if(W[i]!=W[j]) return W[i]<W[j]; return i<j; });
vector<int> pos(N); // pos[original_index] = new index
vector<long long> sW(N), sA(N), sB(N);
for(int i=0;i<N;i++){
pos[ord[i]] = i;
sW[i] = W[ord[i]];
sA[i] = A[ord[i]];
sB[i] = B[ord[i]];
}
// C = A - B
vector<ll> C(N);
ll sumB = 0;
for(int i=0;i<N;i++){ C[i] = sA[i] - sB[i]; sumB += sB[i]; }
// Prepare candidate pairs: (i, i+1) and (i, i+2)
struct PairItem { ll diff; int i; int j; int type; }; // type: 1 = (i,i+1) union, 2 = (i,i+2) enable middle
vector<PairItem> pairs;
for(int i=0;i+1<N;i++){
pairs.push_back({ sW[i+1] - sW[i], i, i+1, 1 });
}
for(int i=0;i+2<N;i++){
pairs.push_back({ sW[i+2] - sW[i], i, i+2, 2 });
}
sort(pairs.begin(), pairs.end(), [](const PairItem &a, const PairItem &b){
if(a.diff!=b.diff) return a.diff < b.diff;
return a.type < b.type;
});
// Sort queries with indexes
vector<int> qidx(Q);
iota(qidx.begin(), qidx.end(), 0);
sort(qidx.begin(), qidx.end(), [&](int a, int b){ if(E[a]!=E[b]) return E[a] < E[b]; return a < b; });
// DSU and per-component info
DSU dsu(N);
// Note: dsu constructor already created parity arrays via push_back. But we need them as vectors sized N and accessible by index.
// Reconstruct DSU fields properly:
// (Because of the push_back hack in constructor creating arrays of size N, but easier to reassign properly.)
dsu = DSU(N);
// initialize parity minima & enabled
for(int i=0;i<N;i++){
int r = dsu.find(i);
dsu.minC_par[0][i] = INF;
dsu.minC_par[1][i] = INF;
int par = i & 1;
dsu.minC_par[par][i] = C[i];
dsu.minIndex[i] = i;
dsu.minEnabled[i] = INF;
dsu.sz[i] = 1;
}
// helper to get component contribution:
auto comp_contrib = [&](int root)->ll{
if(dsu.sz[root] % 2 == 0) return 0;
int L = dsu.minIndex[root];
int par = L & 1;
ll best = min(dsu.minC_par[par][root], dsu.minEnabled[root]);
return best;
};
// but since we store parity minima in arrays indexed by root (and when we merge we write into root entries),
// initial contribution sum is sum C[i]
ll extra_sum = 0;
for(int i=0;i<N;i++) extra_sum += C[i];
// We'll need arrays to check whether an index has been enabled already
vector<char> enabled(N, 0);
// pointer over pairs
int pptr = 0;
vector<ll> ans(Q);
for(int qi = 0; qi < Q; ++qi){
int qid = qidx[qi];
ll D = E[qid];
// process pairs with diff <= D
while(pptr < (int)pairs.size() && pairs[pptr].diff <= D){
auto &pr = pairs[pptr];
if(pr.type == 2){
// (i,i+2) -> enable middle i+1
int mid = pr.i + 1;
if(!enabled[mid]){
enabled[mid] = 1;
int root = dsu.find(mid);
// update extra_sum: remove old contribution, update minEnabled, add new contribution
ll before = comp_contrib(root);
extra_sum -= before;
dsu.minEnabled[root] = min(dsu.minEnabled[root], C[mid]);
ll after = comp_contrib(root);
extra_sum += after;
}
} else {
// (i,i+1) union components
int u = pr.i, v = pr.j;
int ru = dsu.find(u), rv = dsu.find(v);
if(ru != rv){
// remove their contributions
ll before_u = comp_contrib(ru);
ll before_v = comp_contrib(rv);
extra_sum -= (before_u + before_v);
// merge -- keep root ru as the final root (DSU ensures by size)
dsu.unite_roots(ru, rv);
int newr = dsu.find(ru); // root after union (should be ru or swapped)
// If root changed due to size swap inside unite_roots, ensure parity minima etc are at newr already handled
// after unite_roots we have parity mins at new root index
// add new contribution
ll after = comp_contrib(newr);
extra_sum += after;
}
}
pptr++;
}
ans[qid] = sumB + extra_sum;
}
// output answers in original order
for(int i=0;i<Q;i++) cout << ans[i] << '\n';
return 0;
}