Submission #1194193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194193		vincentbucourt1	Nile (IOI24_nile)	C++17	51 / 100	93 ms	24460 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll INF = (ll)1e18;

ll N, Q;
enum typeQ {CONN, JUMP, QUERY};
struct Event {
  typeQ t;
  ll w, i;
};
bool cmpEvents (const Event& a, const Event& b) {
  return tie(a.w, a.t, a.i) < tie(b.w, b.t, b.i);
}
struct Node {
  ll idx, weight, solo, duo;
};
bool cmpNodes (const Node& a, const Node& b) {
  return tie(a.weight, a.idx, a.solo, a.duo) < tie(b.weight, b.idx, b.solo, b.duo);
}
vector<Event> events;
vector<ll> ans;

struct CC {
  ll minEven, minOdd;
  ll minAll;
  ll par, size, l, r;
  ll cost () {
    return (size%2==0 ? 0 : min(minAll, (l%2==0 ? minEven : minOdd)));
  }
};
struct DSU {
  vector<CC> nodes;
  vector<ll> solo, duo;
  ll cost = 0;
  DSU(){}
  DSU (ll n, vector<int>& Ac, vector<int>& Bc) {
    nodes.resize(n);
    copy(Ac.begin(), Ac.end(), back_inserter(solo));
    copy(Bc.begin(), Bc.end(), back_inserter(duo));
    cost = 0ll;
    for (int i = 0; i < N; i++) {
      nodes[i] = CC{(i%2==0 ? solo[i]-duo[i] : INF), (i%2==1 ? solo[i]-duo[i] : INF), INF, i, 1, i, i};
      cost += duo[i];
      cost += nodes[i].cost();
    }
  }
  ll get (ll node) {
    if (nodes[node].par == node) return node;
    else return nodes[node].par = get(nodes[node].par);
  }
  void conn (ll i) {
    ll u = get(i);
    ll v = get(i+1);
    assert(u != v);

    cost -= nodes[u].cost();
    cost -= nodes[v].cost();

    nodes[u].size += nodes[v].size;
    nodes[u].l = min(nodes[u].l, nodes[v].l);
    nodes[u].r = max(nodes[u].r, nodes[v].r);
    nodes[u].minEven = min(nodes[u].minEven, nodes[v].minEven);
    nodes[u].minOdd = min(nodes[u].minOdd, nodes[v].minOdd);
    nodes[v].par = u;

    cost += nodes[u].cost();
  }
  void jump (ll i) {
    ll u = get(i);
    cost -= nodes[u].cost();
    nodes[u].minAll = min(nodes[u].minAll, (ll)(solo[i]-duo[i]));
    cost += nodes[u].cost();
  }
  ll query () {
    return cost;
  }
};

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  N = (ll)W.size();
  Q = (ll)E.size();
  vector<Node> nodes;
  for (ll i = 0; i < N; i++) {
    nodes.push_back(Node{i, W[i], A[i], B[i]});
  }
  sort(nodes.begin(), nodes.end(), cmpNodes);
  // for (ll i = 0; i < N; i++) {
  //   cerr << nodes[i].weight << " ";
  // }
  // cerr << "\n";
  for (ll i = 0; i < N-1; i++) {
    events.push_back({CONN, abs(nodes[i].weight - nodes[i+1].weight), i});
  }
  for (ll i = 0; i < N-2; i++) {
    events.push_back({JUMP, abs(nodes[i].weight - nodes[i+2].weight), i+1});
  }
  for (ll i = 0; i < Q; i++) {
    events.push_back({QUERY, E[i], i});
  }
  sort(events.begin(), events.end(), cmpEvents);
  vector<int> newA, newB;
  for (ll i = 0; i < N; i++) {
    newA.push_back(nodes[i].solo);
    newB.push_back(nodes[i].duo);
  }
  DSU dsu(N, newA, newB);
  ans.resize(Q);
  for (Event event : events) {
    if (event.t == CONN) {
      dsu.conn(event.i);
    }
    else if (event.t == JUMP) {
      dsu.jump(event.i);
    }
    else {
      assert(event.t == QUERY);
      ans[event.i] = dsu.query();
    }
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18