Submission #1254074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254074		erdemkiraz	Nile (IOI24_nile)	C++20	100 / 100	73 ms	9024 KiB

nile

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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e5 + 5;

int n;

int root[N], odd_mn[N], even_mn[N], lf[N], best_mid[N], sz[N];

int f(int x) {
  if(x == root[x]) {
    return x;
  }
  return root[x] = f(root[x]);
}

vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> qd) {
  int q = (int) qd.size();

  n = (int) a.size();
  
  vector<int> ord(n);
  for(int i = 0; i < n; i++) {
    ord[i] = i;
  }
  sort(ord.begin(), ord.end(), [&](int i, int j){
    return w[i] < w[j];
  });

  vector<ii> dists;
  for(int i = 1; i < n; i++) {
    dists.push_back({w[ord[i]] - w[ord[i - 1]], i});
  }
  sort(dists.begin(), dists.end());
  reverse(dists.begin(), dists.end());

  vector<ii> mids;
  for(int i = 1; i + 1 < n; i++) {
    mids.push_back({w[ord[i + 1]] - w[ord[i - 1]], i});
  }
  sort(mids.begin(), mids.end());
  reverse(mids.begin(), mids.end());

  ll add = 0;

  for(int i = 0; i < n; i++) {
    a[i] -= b[i];
    add += b[i];
  }

  ll ans = add;

  for(int i = 0; i < n; i++) {
    root[i] = i; 
    odd_mn[i] = even_mn[i] = 1e9;
    if(i % 2 == 0) {
      even_mn[i] = a[ord[i]];
    }
    else {
      odd_mn[i] = a[ord[i]];
    }

    lf[i] = i;

    sz[i] = 1;

    best_mid[i] = (int) 1e9;

    ans += a[ord[i]];
  }

  vector<int> q_ord(q);
  for(int i = 0; i < q; i++) {
    q_ord[i] = i;
  }
  sort(q_ord.begin(), q_ord.end(), [&](int i, int j){
    return qd[i] < qd[j];
  });

  vector<ll> ret(q, 0);

  auto cost = [&](int x){
    if(sz[x] % 2 == 0) {
      return 0;
    }

    int res = 1e9;

    if(lf[x] % 2 == 0) {
      res = even_mn[x];
    }
    else {
      res = odd_mn[x];
    }

    res = min(res, best_mid[x]);

    return res;
  };

  auto merge = [&](int x, int y){
    root[y] = x;
    sz[x] += sz[y];
    even_mn[x] = min(even_mn[x], even_mn[y]);
    odd_mn[x] = min(odd_mn[x], odd_mn[y]);
    best_mid[x] = min(best_mid[x], best_mid[y]);
  };

  for(int it = 0; it < q; it++) {
    int d = qd[q_ord[it]];

    while((int) dists.size() and dists.back().first <= d) {
      // puts("work");
      int i = dists.back().second;
      dists.pop_back();

      int x = f(i - 1);
      int y = f(i);

      ans -= cost(x);
      ans -= cost(y);

      merge(x, y);

      ans += cost(x);
    }

    while((int) mids.size() and mids.back().first <= d) {
      int i = mids.back().second;
      mids.pop_back();

      int x = f(i);

      ans -= cost(x);

      best_mid[x] = min(best_mid[x], a[ord[i]]);

      ans += cost(x);
    }

    // printf("ans = %lld\n", ans);

    ret[q_ord[it]] = ans;
  }

  return ret;
}

• 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