Submission #1258203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258203		altern23	Nile (IOI24_nile)	C++20	38 / 100	83 ms	22044 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];

struct DSU{
  ll N;
  vector<ll> par, sz, ki, ka, mx, sum;
  DSU(ll _n){
    N = _n;
    par.resize(N + 5), sz.resize(N + 5), ki.resize(N + 5), ka.resize(N + 5), mx.resize(N + 5), sum.resize(N + 5);
    for(int i = 0; i < N; i++){
      par[i] = i;
      sz[i] = 1;
      mx[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[a], Y[ki[a]] - X[ki[a]], Y[ka[a]] - X[ka[a]]}) : 0LL);
      mx[a] = max(mx[a], (val == -1 ? -INF : Y[val] - X[val]));
      ans += sum[a] - (sz[a] % 2 ? max({mx[a], Y[ki[a]] - X[ki[a]], Y[ka[a]] - X[ka[a]]}) : 0LL);
      return;
    }
    
    ans -= sum[a] - (sz[a] % 2 ? max({mx[a], Y[ki[a]] - X[ki[a]], Y[ka[a]] - X[ka[a]]}) : 0LL);
    ans -= sum[b] - (sz[b] % 2 ? max({mx[b], Y[ki[b]] - X[ki[b]], Y[ka[b]] - X[ka[b]]}) : 0LL);

    if(sz[a] < sz[b]) swap(a, b);
    ki[a] = min(ki[a], ki[b]);
    ka[a] = max(ka[a], ka[b]);

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

    mx[a] = max(mx[a], mx[b]);
    mx[a] = max(mx[a], (val == -1 ? -INF : Y[val] - X[val]));
    
    ans += sum[a] - (sz[a] % 2 ? max({mx[a], Y[ki[a]] - X[ki[a]], Y[ka[a]] - X[ka[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++){
    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.mx[i] = dsu.sum[i] = B[i] - A[i];
    dsu.ki[i] = dsu.ka[i] = 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: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18