Submission #1231055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231055		kilikuma	Nile (IOI24_nile)	C++20	100 / 100	96 ms	32544 KiB

nile

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

using namespace std; 

const long long INF = (long long) (1e9);  

struct Info {
  long long l = 0, r = INF, impair = INF, pair = INF, bonus = INF, ans = 0;
}; 

Info combine(Info a, Info b) {
  Info nouv; 
  nouv.l = a.l; 
  nouv.r = b.r; 
  if ((a.r - a.l + 1) % 2 == 0) {
    nouv.impair = min(a.impair, b.impair);
    nouv.pair = min(a.pair, b.pair); 
  }
  else {
    nouv.impair = min(a.impair, b.pair); 
    nouv.pair = min(a.pair, b.impair); 
  }
  nouv.bonus = min(a.bonus, b.bonus); 
  if ((nouv.r - nouv.l + 1) % 2 == 0) {
    nouv.ans = 0; 
  }
  else {
    nouv.ans = min(nouv.impair, nouv.bonus); 
  }
  return nouv; 
}

class UnionFind {
public : 
  vector<Info> infos; 
  vector<long long> parent; 
  long long cur = 0; 
  long long tot = 0; 
  void create(Info nouv) {
    infos.push_back(nouv); 
    parent.push_back(cur); 
    cur ++; 
    tot += nouv.ans; 
  }
  long long racine(long long u) {
    if (parent[u] == u)
      return u; 
    parent[u] = racine(parent[u]); 
    return parent[u]; 
  } 
  void merge(long long a, long long b) {
    long long r1 = racine(a); 
    long long r2 = racine(b); 
    tot -= infos[r1].ans; 
    tot -= infos[r2].ans; 
    parent[r1] = cur; 
    parent[r2] = cur; 
    create(combine(infos[r1], infos[r2])); 
    return;
  }
  void bonif(long long ind, long long val) {
    long long r1 = racine(ind);
    tot -= infos[r1].ans; 
    infos[r1].bonus = min(infos[r1].bonus, val); 
    infos[r1].ans = min(infos[r1].ans, infos[r1].bonus); 
    tot += infos[r1].ans; 
    return;
  }
};

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

  vector<long long> w, a, b, e; 

  for (int i = 0; i < W.size(); i ++) {
    w.push_back(W[i]); 
    a.push_back(A[i]); 
    b.push_back(B[i]); 
  }
  for (int i = 0; i < E.size(); i ++) {
    e.push_back(E[i]); 
  }

  int n = w.size(); 
  vector<pair<long long, long long>> artis(n, {0, 0}); 
  long long rep = 0; 
  for (int i = 0; i < n; i ++) {
    artis[i].first = w[i]; 
    artis[i].second = a[i] - b[i]; 
    rep += b[i]; 
  }
  sort(artis.begin(), artis.end()); 
  vector<pair<long long, long long>> ans; 
  UnionFind goro;  
  for (int i = 0; i < n; i ++) {
    Info nouv; 
    nouv.l = i; 
    nouv.r = i; 
    nouv.impair = artis[i].second; 
    nouv.ans = artis[i].second; 
    goro.create(nouv); 
  }
  ans.push_back({0, goro.tot + rep}); 
  vector<tuple<long long, long long, long long>> events; 
  for (int i = 0; i + 1 < n; i ++) {
    events.push_back({artis[i + 1].first - artis[i].first, 0, i}); 
  }
  for (int i = 1; i + 1 < n; i ++) {
    events.push_back({artis[i + 1].first - artis[i - 1].first, 1, i}); 
  }
  sort(events.begin(), events.end()); 
  for (int i = 0; i < events.size(); i ++) {
    if (get<1>(events[i]) == 0) {
      goro.merge(get<2>(events[i]), get<2>(events[i]) + 1); 
      ans.push_back({get<0>(events[i]), goro.tot + rep}); 
    }
    else {
      goro.bonif(get<2>(events[i]), artis[get<2>(events[i])].second); 
      ans.push_back({get<0>(events[i]), goro.tot + rep}); 
    }
  }
  vector<long long> sus(e.size(), 0ll); 
  for (int i = 0; i < e.size(); i ++) {
    long long lo = 0, hi = ans.size() - 1; 
    while (hi - lo > 1) {
      long long mid = (lo + hi) / 2; 
      if (ans[mid].first <= e[i]) 
        lo = mid; 
      else 
        hi = mid; 
    }
    if (ans[hi].first <= e[i])
      sus[i] = ans[hi].second; 
    else 
      sus[i] = ans[lo].second; 
  }
  return sus; 
}

• 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