제출 #1258388

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

nile

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

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second

const ll INF = 1e18;
const int MAXN = 1e5;

ll ans = 0;
ll X[MAXN + 5], Y[MAXN + 5], idx[MAXN + 5];

struct DSU{
  ll N;
  vector<ll> par, sz, sum, lf;
  vector<ll> mx[2], mx2[2];
  DSU(ll _n){
    N = _n;
    par.resize(N + 5), sz.resize(N + 5), sum.resize(N + 5), lf.resize(N + 5);
    mx[0].resize(N + 5), mx[1].resize(N + 5);
    mx2[0].resize(N + 5), mx2[1].resize(N + 5);
    for(int i = 0; i < N; i++){
      par[i] = i;
      sz[i] = 1;
      mx[0][i] = mx[1][i] = -INF;
      mx2[0][i] = mx2[1][i] = -INF;
      sum[i] = 0;
    }
  }
  ll find(ll idx){
    return par[idx] == idx ? idx : par[idx] = find(par[idx]);
  }
  void join(ll a, ll b, ll val){
    a = find(a), b = find(b);
    if(a == b){
      ans -= sum[a] - (sz[a] % 2 ? max(mx[1 - lf[a] % 2][a], mx2[lf[a] % 2][a]) : 0LL);
      if(val != -1){
        mx[idx[val] % 2][a] = max(mx[idx[val] % 2][a], Y[val] - X[val]);
      }
      ans += sum[a] - (sz[a] % 2 ? max(mx[1 - lf[a] % 2][a], mx2[lf[a] % 2][a]) : 0LL);
      return;
    }
    
    ans -= sum[a] - (sz[a] % 2 ? max(mx[1 - lf[a] % 2][a], mx2[lf[a] % 2][a]) : 0LL);
    ans -= sum[b] - (sz[b] % 2 ? max(mx[1 - lf[b] % 2][b], mx2[lf[b] % 2][b]) : 0LL);

    if(sz[a] < sz[b]) swap(a, b);

    par[b] = a;
    sz[a] += sz[b], sz[b] = 0;
    sum[a] += sum[b], sum[b] = 0;

    lf[a] = min(lf[a], lf[b]);

    if(val != -1) mx[idx[val] % 2][a] = max(mx[idx[val] % 2][a], Y[val] - X[val]);

    mx2[0][a] = max(mx2[0][a], mx2[0][b]);
    mx2[1][a] = max(mx2[1][a], mx2[1][b]);
    mx[0][a] = max(mx[0][a], mx[0][b]);
    mx[1][a] = max(mx[1][a], mx[1][b]);
    
    ans += sum[a] - (sz[a] % 2 ? max(mx[1 - lf[a] % 2][a], mx2[lf[a] % 2][a]) : 0LL);
  }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, std::vector<int> E) {  
  int Q = (int)E.size(), N = (int)W.size();
  vector<ll> R(Q, 0);

  vector<pii> objects;
  for(int i = 0; i < N; i++){
    objects.push_back({W[i], i});
    X[i] = A[i], Y[i] = B[i];
  }
  sort(objects.begin(), objects.end());
  vector<pair<pii, pii>> edges;
  for(int i = 0; i < N; i++){
    idx[objects[i].sec] = i;
    if(i + 1 < N) edges.push_back({{objects[i + 1].fi - objects[i].fi, -1}, {objects[i].sec, objects[i + 1].sec}});
    if(i + 2 < N) edges.push_back({{objects[i + 2].fi - objects[i].fi, objects[i + 1].sec}, {objects[i].sec, objects[i + 2].sec}});
  }
  sort(edges.begin(), edges.end());
  vector<pii> queries;
  
  DSU dsu(N);

  for(int i = 0; i < N; i++){
    dsu.sum[i] = B[i] - A[i];
    dsu.lf[i] = idx[i];
    dsu.mx2[idx[i] % 2][i] = B[i] - A[i];
  }

  for(int i = 0; i < Q; i++) queries.push_back({E[i], i});
  sort(queries.begin(), queries.end());

  ll cur = 0;
  for(int i = 0; i < N; i++) ans += A[i];

  for(auto [val, idx] : queries){
    while(cur < (int)edges.size() && edges[cur].fi.fi <= val){
      dsu.join(edges[cur].sec.fi, edges[cur].sec.sec, edges[cur].fi.sec);
      cur++;
    }
    R[idx] = ans;
  }
  return R;
}

• 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