제출 #1239495

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

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

ari2 operator+(const ari2 &a, const ari2 &b) {
  return {min(a[0], b[0]), min(a[1], b[1])};
}

struct Node {
  int v1; ari2 v2;
  Node operator+(const Node &other) {
    return {min(v1, other.v1), v2 + other.v2};
  }
};

struct ST {
  const int N;
  vt<Node> st;
  ST(const int n) : N(n), st(n << 1, {INT_MAX, ari2{INT_MAX, INT_MAX}}) {}
  void update(int i, const Node v) {
    i += N;
    st[i] = st[i] + v;
    while (i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node ret = {INT_MAX, ari2{INT_MAX, INT_MAX}};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ret = ret + st[l++];
      if (r & 1)
        ret = ret + st[--r];
    }
    return ret;
  }
};

vt<ll> calculate_costs(vt<int> W, vt<int> A, vt<int> B, vt<int> E) {
  const int N = size(W), Q = size(E);
  if (N == 1)
    return vt<ll>(Q, A[0]);
  ll sum = 0;
  {
    vt<int> ord(N);
    iota(all(ord), 0);
    sort(all(ord), [&](const int &a, const int &b) {
      return W[a] < W[b];    
    });
    vt<int> _W(N), _A(N), _B(N);
    FOR(i, 0, N-1) {
      _W[i] = W[ord[i]];
      _A[i] = A[ord[i]];
      _B[i] = B[ord[i]];
      sum += B[i];
    }
    W = _W, A = _A, B = _B;
    #ifdef DEBUG
    cout << "W: ";
    FOR(i, 0, N-1)
      cout << W[i] << "\n "[i+1<N];
    cout << "A: ";
    FOR(i, 0, N-1)
      cout << A[i] << "\n "[i+1<N];
    cout << "B: ";
    FOR(i, 0, N-1)
      cout << B[i] << "\n "[i+1<N];
    #endif
  }
  
  vt<int> sweep(N-1);
  iota(all(sweep), 0);
  sort(all(sweep), [&](const int &a, const int &b) {
    return W[a+1] - W[a] < W[b+1] - W[b];    
  });
  
  vt<int> sweep2(N-2);
  iota(all(sweep2), 0);
  sort(all(sweep2), [&](const int &a, const int &b) {
    return W[a+2] - W[a] < W[b+2] - W[b];    
  });
  
  vt<int> ord(Q);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return E[a] < E[b];    
  });
  
  ST st(N);
  FOR(i, 0, N-1)
    st.update(i, Node{INT_MAX, ari2{i & 1 ? INT_MAX : A[i] - B[i], i & 1 ? A[i] - B[i] : INT_MAX}});
  
  vt<int> L(N), R(N);
  iota(all(L), 0);
  iota(all(R), 0);
  
  const auto cost = [&](const int l, const int r) {
    const Node v = st.query(l, r);
    return r - l & 1 ? 0 : min(v.v1, v.v2[l & 1]);
  };
  
  vt<int> cost_as_L(N), cost_as_R(N);
  ll tot = 0;
  set<ari2> ranges;
  FOR(i, 0, N-1) {
    tot += (cost_as_L[i] = cost_as_R[i] = A[i] - B[i]);
    ranges.insert({i, i});
  }
  
  vt<ll> ans(Q);
  int ptr = 0, ptr2 = 0;
  for (const auto &i : ord) {
    for (; ptr2 < N - 2 && W[sweep2[ptr2] + 2] - W[sweep2[ptr2]] <= E[i]; ptr2++) {
      const int x = sweep2[ptr2] + 1;
      st.update(x, Node{A[x] - B[x], ari2{INT_MAX, INT_MAX}});
      const auto [l, r] = *--ranges.lower_bound({x+1, -1});
      tot -= cost_as_L[l];
      tot += (cost_as_L[l] = cost_as_R[r] = cost(l, r));
    }
    #ifdef DEBUG
    cout << "bruh: " << E[i] << ' ' << cost(0, N-1) << '\n';
    #endif
    for (; ptr < N - 1 && W[sweep[ptr] + 1] - W[sweep[ptr]] <= E[i]; ptr++) {
      const int x = sweep[ptr];
      ranges.erase(ranges.find({L[x], x}));
      ranges.erase(ranges.find({x+1, R[x+1]}));
      tot -= cost_as_L[L[x]];
      tot -= cost_as_R[R[x+1]];
      tot += (cost_as_L[L[x]] = cost_as_R[R[x+1]] = cost(L[x], R[x+1]));
      assert(R[x] == x);
      assert(L[x+1] == x+1);
      L[R[x+1]] = L[x];
      R[L[x]] = R[x+1];
      ranges.insert({L[x], R[x+1]});
    }
    ans[i] = tot + sum;
  }
  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