Submission #1174092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174092		_ncng.nyr	Nile (IOI24_nile)	C++20	100 / 100	139 ms	36820 KiB

nile

#include<bits/stdc++.h>

#define ii pair<long long, long long>
#define tp tuple<long long, long long, long long>

using namespace std;

const long long N = 2e5 + 5;
const long long oo = 1e16;

long long n, Q;
long long a[N], b[N], w[N], e[N], sum[N], f[N];
long long sz[N], par[N], le[N], ri[N];

struct SegmentTree {
  long long T[N << 2];

  void build(long long s, long long l, long long r) {
    if(l == r) {
      T[s] = oo;
      return;
    }
    long long mid = l + r >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
    T[s] = oo;
  }

  void upd(long long s, long long l, long long r, long long p, long long x) {
    if(r < p || l > p) return;
    if(l == r) {
      T[s] = x;
      return;
    }
    long long mid = l + r >> 1;
    upd(s << 1, l, mid, p, x); upd(s << 1 | 1, mid + 1, r, p, x);
    T[s] = min(T[s << 1], T[s << 1 | 1]);
  }

  long long get(long long s, long long l, long long r, long long u, long long v) {
    if(r < u || l > v) return oo;
    if(l >= u && r <= v) return T[s];
    long long mid = l + r >> 1;
    return min(get(s << 1, l, mid, u, v), get(s << 1 | 1, mid + 1, r, u, v));
  }
} st, it[2];


long long fin(long long i) {
  return i == par[i] ? i : i = fin(par[i]);
}

void join(long long u, long long v, long long val) {
  u = fin(u); v = fin(v);
  if(u == v) return;
  if(sz[u] < sz[v]) swap(u, v);
  sz[u] += sz[v]; par[v] = u;
  le[u] = min(le[u], le[v]); ri[u] = max(ri[u], ri[v]);
  sum[u] += sum[v];
  f[u] = val;
}

namespace AC {
  long long res = 0;
  tp item[N];
  ii query[N];
  long long ans[N];
  vector<long long> ret;
  vector<long long> cont[N], bridge[N];

  void init() {
    st.build(1, 1, n); it[0].build(1, 1, n); it[1].build(1, 1, n);
    for(int i = 1; i <= n; ++i) {
      sz[i] = 1; par[i] = le[i] = ri[i] = i;
      auto [w, x, y] = item[i];
      sum[i] = y; f[i] = x;

      it[i & 1].upd(1, 1, n, i, x - y);
    }
  }

  vector<long long> solve() {
    for(int i = 1; i <= n; ++i) item[i] = {w[i], a[i], b[i]}, res += a[i];
    for(int i = 1; i <= Q; ++i) query[i] = {e[i], i};

    sort(item + 1, item + n + 1);
    sort(query + 1, query + Q + 1);

    for(int i = 2; i <= n; ++i) {
      auto [w, x, y] = item[i];
      auto [_w, _x, _y] = item[i - 1];

      long long l = 1, r = Q, idx = 0;
      while(l <= r) {
        long long mid = l + r >> 1;
        if(w - _w <= query[mid].first) idx = mid, r = mid - 1;
        else l = mid + 1;
      }
      if(idx) cont[idx].push_back(i);
    }

    for(int i = 2; i < n; ++i) {
      auto [w, x, y] = item[i - 1];
      auto [_w, _x, _y] = item[i + 1];

      long long l = 1, r = Q, idx = 0;
      while(l <= r) {
        long long mid = l + r >> 1;
        if(_w - w <= query[mid].first) idx = mid, r = mid - 1;
        else l = mid + 1;
      }
      if(idx) bridge[idx].push_back(i);
    }

    init();

    for(long long idx = 1; idx <= Q; ++idx) {
      auto [D, id] = query[idx];
      for(auto i : bridge[idx]) {
        auto [w, x, y] = item[i];
        st.upd(1, 1, n, i, x - y);
        long long u = fin(i - 1), v = fin(i + 1);

        if(u == v) {
          res -= f[u];

          long long val = 0;
          if((ri[v] - le[u] + 1) & 1) {
            long long add = min(st.get(1, 1, n, le[u] + 1, ri[v] - 1), it[le[u] & 1].get(1, 1, n, le[u], ri[v]));
//            long long add = st.get(1, 1, n, le[u] + 1, ri[v] - 1);

            auto [w_, x_, y_] = item[le[u]];
            add = min(add, x_ - y_);
            auto [_w, _x, _y] = item[ri[v]];
            add = min(add, _x - _y);

            val = sum[u] + add;
          }
          else val = sum[u];
          f[u] = val;
          res += val;
        }
      }

      for(auto i : cont[idx]) {
        long long u = fin(i - 1), v = fin(i);
        res -= f[u] + f[v];
        long long val = 0;

        if((ri[v] - le[u] + 1) & 1) {
          long long add = min(st.get(1, 1, n, le[u] + 1, ri[v] - 1), it[le[u] & 1].get(1, 1, n, le[u], ri[v]));
//          long long add = st.get(1, 1, n, le[u] + 1, ri[v] - 1);

          auto [w, x, y] = item[le[u]];
          add = min(add, x - y);
          auto [_w, _x, _y] = item[ri[v]];
          add = min(add, _x - _y);

          val = sum[u] + sum[v] + add;
        }
        else val = sum[u] + sum[v];
        res += val;
        join(u, v, val);
      }

      ans[id] = res;
    }

    for(int i = 1; i <= Q; ++i) ret.push_back(ans[i]);
    return ret;
  }
}

vector<long long> calculate_costs(
    vector<int> W, vector<int> A,
    vector<int> B, vector<int> E) {

  n = W.size(); Q = E.size();

  for(int i = 1; i <= n; ++i)
    w[i] = W[i - 1], a[i] = A[i - 1], b[i] = B[i - 1];

  for(int i = 1; i <= Q; ++i) e[i] = E[i - 1];

  return AC :: solve();
}

//#define ntc
#ifdef ntc
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if(fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  vector<int> W, A, B, E;

  cin >> n;
  for(int i = 1; i <= n; ++i) {
    long long w, a, b; cin >> w >> a >> b;
    W.push_back(w); A.push_back(a); B.push_back(b);
  }

  cin >> Q;
  for(int i = 1; i <= Q; ++i) {
    long long D; cin >> D;
    E.push_back(D);
  }

  vector<long long> ans = calculate_costs(W, A, B, E);
  for(auto x : ans) cout << x << '\n';
}
#endif

• 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