Submission #1231014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231014		kilikuma	Nile (IOI24_nile)	C++20	0 / 100	42 ms	16332 KiB

nile

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

using namespace std; 

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

struct Info {
  int 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<int> parent; 
  int cur = 0; 
  long long tot = 0; 
  void create(Info nouv) {
    infos.push_back(nouv); 
    parent.push_back(cur); 
    cur ++; 
    tot += nouv.ans; 
  }
  int racine(int u) {
    if (parent[u] == u)
      return u; 
    parent[u] = racine(parent[u]); 
    return parent[u]; 
  } 
  void merge(int a, int b) {
    int r1 = racine(a); 
    int 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(int ind, int val) {
    int 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) {
  int n = w.size(); 
  vector<pair<int, int>> 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<int, int>> 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<int, int, int>> 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}); 
    }
  }
  assert(get<0>(events.back()) == 0); 
  
  Info brr = goro.infos[goro.racine(0)]; 
  assert((brr.r - brr.l) == (n - 1));
  
  assert((n % 2) == 1); 
  
  vector<long long> sus(e.size(), 0); 
  for (int i = 0; i < e.size(); i ++) {
    int lo = 0, hi = ans.size() - 1; 
    while (hi - lo > 1) {
      int 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: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18