Submission #1192011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192011		janson0109	Nile (IOI24_nile)	C++20	100 / 100	92 ms	26952 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second

ll find(vector<ll> &p, ll x) {return p[x] == x ? x : find(p, p[x]);}
void unite(vector<ll> &p, vector<ll> &s, vector<ll> &pt, vector<vector<ll>> &d1m, vector<vector<ll>> &d2m, ll x, ll y) {
  ll x_root = find(p,x);
  ll y_root = find(p,y);
  if(x_root == y_root) return;
  pt[max(x_root, y_root)] = pt[min(x_root, y_root)];
  if(s[x_root] < s[y_root]) swap(x_root, y_root);
  s[x_root] += s[y_root];
  p[y_root] = x_root;
  d1m[x_root] = {min(d1m[x_root][0], d1m[y_root][0]), min(d1m[x_root][1], d1m[y_root][1])};
  d2m[x_root] = {min(d2m[x_root][0], d2m[y_root][0]), min(d2m[x_root][1], d2m[y_root][1])};
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  ll q = E.size();
  ll n = W.size();
  ll sum = 0;
  for(ll i=0; i<n; i++) sum += A[i];
  std::vector<long long> R(q, 0);
  vector<pair<ll,ll>> ws(n);
  for(ll i=0; i<n; i++) ws[i] = make_pair(W[i], i);
  sort(ws.begin(), ws.end());
  vector<ll> w(n), a(n), b(n);
  for(ll i=0; i<n; i++) {
    w[i] = ws[i].F;
    a[i] = A[ws[i].S];
    b[i] = B[ws[i].S];
  }
  vector<pair<ll,ll>> d1(n-1);
  vector<pair<ll,ll>> d2(n-2);
  for(ll i=0; i<n-1; i++) {
    d1[i] = make_pair(w[i+1] - w[i], i);
    if(i < n-2) d2[i] = make_pair(w[i+2] - w[i], i);
  }
  sort(d1.begin(), d1.end());
  sort(d2.begin(), d2.end());

  vector<ll> parents(n);
  vector<ll> parity(n);
  vector<vector<ll>> d1m(n, {LLONG_MAX, LLONG_MAX}), d2m(n, {LLONG_MAX, LLONG_MAX});
  vector<ll> scores(n);
  vector<ll> sizes(n, 1);
  iota(parents.begin(), parents.end(),0);
  for(ll i=0; i<n; i++) {parity[i] = i %2; d1m[i][i % 2] = a[i]-b[i]; scores[i] = a[i]-b[i];}

  vector<pair<ll,ll>> e(q);
  for(ll i=0; i<q; i++) e[i] = make_pair(E[i], i);
  sort(e.begin(), e.end());
  ll d1r=0, d2r = 0;
  for(ll i=0; i<q; i++) {
    while(d2r < n-2 && d2[d2r].F <= e[i].F) {
      ll d2i = d2[d2r].S + 1;
      ll d2root = find(parents, d2i);
      d2m[d2root][d2i % 2] = min(d2m[d2root][d2i % 2], a[d2i] - b[d2i]);
      ll nscore = sizes[d2root] % 2 == 0 ? 0 : min(d1m[d2root][parity[d2root]], d2m[d2root][1-parity[d2root]]);
      sum += (nscore - scores[d2root]);
      scores[d2root] = nscore;
      d2r++;
    }

    while(d1r < n-1 && d1[d1r].F <= e[i].F) {
      ll d1r1 = find(parents, d1[d1r].S), d1r2 = find(parents, d1[d1r].S+1);
      unite(parents, sizes, parity, d1m, d2m, d1[d1r].S, d1[d1r].S+1);
      ll d1root = find(parents, d1r1);
      ll nscore = sizes[d1root] % 2 == 0 ? 0 : min(d1m[d1root][parity[d1root]], d2m[d1root][1-parity[d1root]]);
      sum += (nscore - scores[d1r1] - scores[d1r2]);
      scores[d1root] = nscore;
      d1r++;
    }
    R[e[i].S] = sum;
  }
  return R;
}

• 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