제출 #1194440

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

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

struct DSU
{
  vector<int> e, mn, sum;
  vector<array<int, 2>> pos;
  void init(int n)
  {
    e.assign(n, -1);
    sum.assign(n, 0);
    mn.assign(n, inf);
    pos.assign(n, {inf, inf});
  }
  int get(int x)
  {
    if (e[x] < 0) return x;
    return e[x] = get(e[x]);
  }
  int getsum(int x)
  {
    x = get(x);
    if ((-e[x]) & 1) return sum[x] + min(mn[x], pos[x][0]);
    else return sum[x];
  }
  void upd(int x, int val)
  {
    mn[get(x)] = min(mn[get(x)], val);
  }
  void unite(int x, int y)
  {
    x = get(x), y = get(y);
    if (x == y) return;
    array<int, 2> nw = pos[x];
    nw[0] = min(nw[0], pos[y][(-e[x]) & 1]), nw[1] = min(nw[1], pos[y][(-e[x] + 1) & 1]);
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    sum[x] += sum[y];
    mn[x] = min(mn[x], mn[y]);
    pos[x] = nw;
    e[y] = x;
  }
};

vector<long long> calculate_costs(vector<int32_t> W, vector<int32_t> A, vector<int32_t> B, vector<int32_t> E) 
{
  vector<array<int, 3>> w;
  vector<array<int, 2>> q;
  vector<array<int, 2>> un, ed;
  for (int i = 0; i < W.size(); i++) w.push_back({W[i], A[i], B[i]});
  for (int i = 0; i < E.size(); i++) q.push_back({E[i], i});
  int n = w.size(), Q = q.size();
  sort(w.begin(), w.end()), sort(q.begin(), q.end());
  for (int i = 1; i + 1 < w.size(); i++) un.push_back({w[i + 1][0] - w[i - 1][0], i});
  for (int i = 0; i + 1 < w.size(); i++) ed.push_back({w[i + 1][0] - w[i][0], i});
  sort(un.begin(), un.end()), sort(ed.begin(), ed.end());
  DSU dsu;
  dsu.init(n);
  int res = 0;
  for (int i = 0; i < n; i++) dsu.sum[i] = w[i][2], dsu.pos[i][0] = w[i][1] - w[i][2], res += w[i][1];
  vector<int> ans(Q);
  for (int i = 0, j = 0, k = 0; i < Q; i++) 
  {
    while (k < ed.size() && ed[k][0] <= q[i][0])
    {
      res -= dsu.getsum(ed[k][1]) + dsu.getsum(ed[k][1] + 1);
      dsu.unite(ed[k][1], ed[k][1] + 1);
      res += dsu.getsum(ed[k][1]);
      k++;
    }
    while (j < un.size() && un[j][0] <= q[i][0])
    {
      res -= dsu.getsum(un[j][1]);
      dsu.upd(un[j][1], w[un[j][1]][1] - w[un[j][1]][2]);
      res += dsu.getsum(un[j][1]);
      j++;
    }
    ans[q[i][1]] = res;
  }
  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