Submission #1139912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139912		repmann	나일강 (IOI24_nile)	C++20	100 / 100	77 ms	13640 KiB

nile

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, Q;
struct NODE
{
  int parent, ranking;
  int L, R;
  ll min0, min1, best, sum;
}DSU[100096];
struct EDGE
{
  int u, v;
  ll w;
}E[200096];
inline bool comp(EDGE e1, EDGE e2) {return e1.w < e2.w;}
inline ll Get(int i)
{
  if((DSU[i].R - DSU[i].L) & 1) return DSU[i].sum;
  if(DSU[i].L & 1) return DSU[i].sum + min(DSU[i].best, DSU[i].min1);
  return DSU[i].sum + min(DSU[i].best, DSU[i].min0);
}
inline int Find(int i)
{
  while(DSU[i].parent != i) i = DSU[i].parent;
  return i;
}
inline ll Union(int u, int v)
{
  u = Find(u);
  v = Find(v);
  if(u == v) return 0;
  ll RET = Get(u) + Get(v);
  if(DSU[u].ranking < DSU[v].ranking) swap(u, v);
  DSU[u].ranking += DSU[u].ranking == DSU[v].ranking;
  DSU[v].parent = u;
  DSU[u].L = min(DSU[v].L, DSU[u].L);
  DSU[u].R = max(DSU[v].R, DSU[u].R);
  DSU[u].min0 = min(DSU[v].min0, DSU[u].min0);
  DSU[u].min1 = min(DSU[v].min1, DSU[u].min1);
  DSU[u].best = min(DSU[v].best, DSU[u].best);
  DSU[u].sum += DSU[v].sum;
  RET -= Get(u);
  return RET;
}
vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> QR)
{
  N = W.size();
  Q = QR.size();
  vector <ll> O(Q);
  vector <pair <int, int>> MO(Q), V(N);
  for(int i = 0; i < Q; i++) MO[i] = {QR[i], i};
  sort(MO.begin(), MO.end());
  for(int i = 0; i < N; i++) V[i] = {W[i], i};
  sort(V.begin(), V.end());
  for(int i = 1; i < N; i++) E[++M] = {V[i - 1].second, V[i].second, V[i].first - V[i - 1].first};
  for(int i = 2; i < N; i++) E[++M] = {V[i - 1].second, -1, V[i].first - V[i - 2].first};
  sort(E + 1, E + M + 1, comp);
  for(int i = 0; i < N; i += 2) DSU[V[i].second] = {V[i].second, 0, i, i, A[V[i].second] - B[V[i].second], 1LL << 60, 1LL << 60, B[V[i].second]};
  for(int i = 1; i < N; i += 2) DSU[V[i].second] = {V[i].second, 0, i, i, 1LL << 60, A[V[i].second] - B[V[i].second], 1LL << 60, B[V[i].second]};
  ll temp = 0;
  for(int i = 0; i < N; i++) temp += A[i];
  int i = 1;
  for(pair <int, int> p : MO)
  {
    while((i <= M) && (E[i].w <= p.first))
    {
      if(E[i].v >= 0) temp -= Union(E[i].u, E[i].v);
      else
      {
        E[i].v = Find(E[i].u);
        temp -= Get(E[i].v);
        DSU[E[i].v].best = min(1LL * (A[E[i].u] - B[E[i].u]), DSU[E[i].v].best);
        temp += Get(E[i].v);
      }
      i++;
    }
    O[p.second] = temp;
  }
  return O;
}

• 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