Submission #1103570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103570		duckindog	Nile (IOI24_nile)	C++17	100 / 100	169 ms	26568 KiB

nile

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "nile.h"
#endif

const int N = 100'000 + 10;
struct DSU { 
  int id[N];

  DSU() { 
    memset(id, -1, sizeof id);
  }

  int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
  void add(int u, int v) { 
    u = root(u); v = root(v);
    if (u == v) return;
    id[u] += id[v];
    id[v] = u;
  }
} fwd, bwd;

int n;
struct Artifact { 
  int w, a, b;
} p;

const long long MAX = 1'000'000'000'000'000;
struct IT { 
  long long f[N << 2];

  IT() { 
    memset(f, 14, sizeof f);
  }

  void update(int s, int l, int r, int p, int x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s] = x;
      return;
    }
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
    f[s] = min(f[s << 1], f[s << 1 | 1]);
  }
  long long query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return MAX;
    if (u <= l && r <= v) return f[s];
    int mid = (l + r) >> 1;
    return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
} T[2], D[2];

using Tp = tuple<int, int, int>;
priority_queue<Tp, vector<Tp>, greater<>> s;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<>> f[2];

vector<long long> calculate_costs(vector<int> W, vector<int> A,
                                  vector<int> B, vector<int> E) {
  int n = W.size();
  vector<Artifact> p(n);
  for (int i = 0; i < n; ++i) p[i] = {W[i], A[i], B[i]}; 
  
  int q = E.size();
  vector<pair<int, int>> queries(q);
  for (int i = 0; i < q; ++i) queries[i] = {E[i], i};
  
  vector<long long> answer(q);
  
  sort(queries.begin(), queries.end());
  sort(p.begin(), p.end(), [&](const auto& a, const auto& b) { return a.w > b.w; });
  vector<long long> d(n);
  for (int i = 0; i < n; ++i) { 
    if (i) d[i] = d[i - 1];
    d[i] += p[i].b;
  }
  
  auto cal = [&](int l, int r) { 
    if (r - l + 1 == 1) return 1ll * p[l].a;
    if (r - l + 1 == 2) return 1ll * p[l].b + p[r].b;
    
    long long value = d[r] - d[l] + p[l].b;
    if (!((r - l + 1) & 1)) return value;
    int type = l & 1;
    return value + min(T[type].query(1, 0, n - 1, l, r), 
                        D[type ^ 1].query(1, 0, n - 1, l + 1, r - 1));
  };
  
  for (int i = 1; i < n; ++i) s.push(make_tuple(p[i - 1].w - p[i].w, i - 1, i));
  for (int i = 1; i < n - 1; ++i) f[i & 1].push(make_pair(p[i - 1].w - p[i + 1].w, i));
  for (int i = 0; i < n; ++i) T[i & 1].update(1, 0, n - 1, i, p[i].a - p[i].b);

  long long total = 0;
  for (int i = 0; i < n; ++i) total += cal(i, i);
  // cerr << total << "\n";
  for (int i = 0; i < q; ++i) {
    const auto& [d, idx] = queries[i];

    { //update
      while (s.size() && get<0>(s.top()) <= d) { 
        auto [cmp, r1, l2] = s.top(); s.pop();
        int l1 = bwd.root(r1), r2 = fwd.root(l2);

        total -= cal(l1, r1);     
        total -= cal(l2, r2);
        
        bwd.add(r1, l2); 
        fwd.add(l2, r1);

        int l = bwd.root(r1), r = fwd.root(l2);
        total += cal(l, r);     
      }

      for (int type = 0; type <= 1; ++type) { 
        while (f[type].size() && get<0>(f[type].top()) <= d) { 
          auto [cmp, pos] = f[type].top(); f[type].pop();
          int l = bwd.root(pos), r = fwd.root(pos);
          
          total -= cal(l, r);
          D[type].update(1, 0, n - 1, pos, p[pos].a - p[pos].b);
          total += cal(l, r);
        }
      }
    }
    answer[idx] = total;
  }

  return answer;
}

#ifdef LOCAL
int32_t main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> W(N), A(N), B(N);
  for (int i = 0; i < N; i++)
    assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> E(Q);
  for (int j = 0; j < Q; j++)
    assert(1 == scanf("%d", &E[j]));
  fclose(stdin);

  std::vector<long long> R = calculate_costs(W, A, B, E);

  int S = (int)R.size();
  for (int j = 0; j < S; j++)
    printf("%lld\n", R[j]);
  fclose(stdout);

  return 0;
}
#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