Submission #1205342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205342		Gabp	Wiring (IOI17_wiring)	C++20	100 / 100	92 ms	15220 KiB

wiring

#include<bits/stdc++.h>
using namespace std;

const long long int INF = 1e18;

struct SegTree {
  int n;
  vector<long long int> st, lazy;
  
  SegTree(int n) : n(n) {
    st.assign(4 * n, 0);
    lazy.assign(4 * n, 0);
  }
  
  void push(int v) {
    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    st[2 * v] += lazy[v];
    st[2 * v + 1] += lazy[v];
    lazy[v] = 0;
  }
  
  void update(int v, int tl, int tr, int l, int r, long long int add) {
    if (l > r) return;
    if (tl == l && tr == r) {
      st[v] += add;
      lazy[v] += add;
      return;
    }
    
    push(v);
    int mid = tl + (tr - tl) / 2;
    update(2 * v, tl, mid, l, min(mid, r), add);
    update(2 * v + 1, mid + 1, tr, max(mid + 1, l), r, add);
    st[v] = min(st[2 * v], st[2 * v + 1]);
  }
  
  void update(int l, int r, long long int add) {
    update(1, 0, n - 1, max(0, l), min(r, n - 1), add);
  }
  
  long long int query() {
    return st[1];
  }
};

long long int min_total_length(vector<int> r, vector<int> b) {
  if (r[0] > b[0]) swap(r, b);
  
  int n = r.size(), m = b.size();
  int p1 = 0, p2 = 0;
  
  vector<vector<int>> a;
  while (p1 < n || p2 < m) {
    vector<int> temp;
    while (p1 < n && (p2 == m || r[p1] < b[p2])) {
      temp.push_back(r[p1++]);
    }
    a.push_back(temp);
    
    swap(p1, p2);
    swap(r, b);
    swap(n, m);
  }
  
  n = a.size();
  long long int total = 0;
  for (auto i: a[0]) {
    total += a[1][0] - i;
  }
  int cnt = a[0].size();
  SegTree st(cnt + 1);
  st.update(0, cnt - 1, INF);
  st.update(cnt, cnt, total);
  
  for (int i = 1; i < n - 1; i++) {
    cnt = a[i].size();
    total = 0;
    for (auto id: a[i]) {
      total += a[i + 1][0] - id;
    }
    
    vector<long long int> dp(cnt + 1);
    dp[cnt] = st.query() + total;
    for (int j = 0; j < cnt; j++) {
      total -= a[i + 1][0] - a[i][j];
      st.update(0, j, a[i][j] - a[i - 1].back());
      st.update(j + 1, st.n - 1, a[i][j] - a[i][0]);
      
      dp[cnt - 1 - j] = st.query() + total;
    }
    
    SegTree nst(cnt + 1);
    for (int j = 0; j <= cnt; j++) nst.update(j, j, dp[j]);
    st = move(nst);
  }
  
  cnt = a[n - 1].size();
  for (int i = 0; i < cnt; i++) {
    st.update(0, i, a[n - 1][i] - a[n - 2].back());
    st.update(i + 1, st.n - 1, a[n - 1][i] - a[n - 1][0]);
  }
  
  return st.query();
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45