Submission #1174047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174047		_ncng.nyr	Nile (IOI24_nile)	C++20	32 / 100	140 ms	29924 KiB

nile

#include<bits/stdc++.h>

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

using namespace std;

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

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

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

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

  void upd(int s, int l, int r, int p, int x) {
    if(r < p || l > p) return;
    if(l == r) {
      T[s] = x;
      return;
    }
    int 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(int s, int l, int r, int u, int v) {
    if(r < u || l > v) return oo;
    if(l >= u && r <= v) return T[s];
    int mid = l + r >> 1;
    return min(get(s << 1, l, mid, u, v), get(s << 1 | 1, mid + 1, r, u, v));
  }
} st;



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

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

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

  void init() {
    st.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;
    }
  }

  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];

      int l = 1, r = Q, idx = 0;
      while(l <= r) {
        int 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];

      int l = 1, r = Q, idx = 0;
      while(l <= r) {
        int 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);
    }
//
//    for(int i = 1; i <= n; i ++) {
//      auto [w, a, b] = item[i];
//
//      cerr << w << " " << a << " " << b << " g\n";
//    }
//    cerr << " \n";

    init();

    for(int idx = 1; idx <= Q; ++idx) {
      auto [D, id] = query[idx];
      for(auto i : bridge[idx]) {
           auto [w, x, y] = item[i];
//        auto [w, a, b] = item[i - 1];
//        auto [_w, _a, _b] = item[i + 1];
        st.upd(1, 1, n, i, x - y);
      }

//      cerr << idx << " check\n";

      for(auto i : cont[idx]) {
        int u = fin(i - 1), v = fin(i);
        res -= f[u] + f[v];
        long long val = 0;
//        cerr << ri[v] << " " << le[u] << " t\n";
        if((ri[v] - le[u] + 1) & 1) {
          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);
//          cerr << add << " r\n";
//          cerr << sum[u] << " " << sum[v] << " ererer\n";
          val = sum[u] + sum[v] + add;
        }
        else val = sum[u] + sum[v];
//        cerr << u << " " << v << " " << sum[u] << " " << sum[v] << " yryryryry\n";
        res += val;
//        cerr << i << " " << res << " y\n";
        join(u, v, val);
      }
//      cerr << res << " det\n";
      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) {
    int 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) {
    int 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: 0 / 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