Submission #645074

#	Time	Username	Problem	Language	Result	Execution time	Memory
645074		slime	Wiring (IOI17_wiring)	C++14	100 / 100	227 ms	85400 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
struct segtree_basic {
  struct node {
    int lazyval, mi, ma, sum; char lazytag;
    int len; // not changing
  };
  int stok;
  vector<node> st;
  void bu(int l, int r, int idx) {
    st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
    st[idx].lazytag = '?';
    st[idx].len = r - l + 1;
    if(l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    bu(l, mid, 2*idx+1);
    bu(mid+1, r, 2*idx+2);
  }
  void push_down(int idx) {
    if(st[idx].lazytag == '?') return;
    if(st[idx].lazytag == ':') {
      st[2*idx+1].lazyval = st[idx].lazyval;
      st[2*idx+1].mi = st[idx].lazyval;
      st[2*idx+1].ma = st[idx].lazyval;
      st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = ':';
 
      st[2*idx+2].lazyval = st[idx].lazyval;
      st[2*idx+2].mi = st[idx].lazyval;
      st[2*idx+2].ma = st[idx].lazyval;
      st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = ':';
 
    }
    else {
      st[2*idx+1].lazyval += st[idx].lazyval;
      st[2*idx+1].mi += st[idx].lazyval;
      st[2*idx+1].ma += st[idx].lazyval;
      st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
 
      st[2*idx+2].lazyval += st[idx].lazyval;
      st[2*idx+2].mi += st[idx].lazyval;
      st[2*idx+2].ma += st[idx].lazyval;
      st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
    }
    st[idx].lazytag = '?';
    st[idx].lazyval = 0;
  }
  void push_up(int idx) {
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
  }
  void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
    if(l <= constl && constr <= r) {
      st[idx].lazyval = val;
      st[idx].mi = val;
      st[idx].ma = val;
      st[idx].sum = val * st[idx].len;
      st[idx].lazytag = ':';
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
    else {
      u1(l, r, constl, mid, 2*idx+1, val);
      u1(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
    if(l <= constl && constr <= r) {
      st[idx].lazyval += val;
      st[idx].mi += val;
      st[idx].ma += val;
      st[idx].sum += val * st[idx].len;
      st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
    else {
      u2(l, r, constl, mid, 2*idx+1, val);
      u2(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  int qu1(int l, int r, int constl, int constr, int idx) { // range min
    if(l <= constl && constr <= r) return st[idx].mi;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1);
    else {
      return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
    }
  }
 
  int qu2(int l, int r, int constl, int constr, int idx) { // range max
    if(l <= constl && constr <= r) return st[idx].ma;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2); 
    else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1);
    else {
      return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
    }
  }
  int qu3(int l, int r, int constl, int constr, int idx) { // range sum
    if(l <= constl && constr <= r) return st[idx].sum;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1);
    else {
      return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2);
    }
  }
  int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu4(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu4(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1;
        else constl = mid+1, idx = 2*idx + 2;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchild = qu5(l, r, constl, mid, 2*idx+1, val);
      if(lchild != -1) return lchild;
      return qu5(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu6(l, r, constl, mid, 2*idx+1, val);
    }
  }
  int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu7(l, r, constl, mid, 2*idx+1, val);
    }
  }
  public:
  void resize(int k) {
    st.resize(4*k + 10);
    stok = k;
    bu(0, k, 0);
  }
  void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
 
  void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
 
  int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
 
  int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); }
 
  int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
 
  int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
 
  int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
 
  int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); } 
 
  int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
long long ps[MAXN];
long long f(int l1, int r1, int l2, int r2) {
  long long cntB = r2 - l2 + 1;
  long long cntR = r1 - l1 + 1;
  long long sumB = ps[r2] - ps[l2 - 1];
  long long sumR = ps[r1] - ps[l1 - 1];
  if(cntR <= cntB) {
    return sumB - sumR - (cntB - cntR) * (ps[r1] - ps[r1 - 1]);
    // sumB - sumR - cntB * a[r1] + cntR * a[r1]
  }
  else {
    return sumB - sumR + (cntR - cntB) * (ps[l2] - ps[l2 - 1]);
  }
}

long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
  vector<pair<long long, char> > all;
  all.push_back({-1, 'N'});
  for(int i=0; i<r.size(); i++) all.push_back({r[i], 'R'});
  for(int i=0; i<b.size(); i++) all.push_back({b[i], 'B'});
  sort(all.begin(), all.end());
  int n = all.size() - 1;
  long long dp[n+1];
  ps[0] = 0;
  for(int i=1; i<=n; i++) ps[i] = ps[i-1] + all[i].first;
  segtree_basic case1, case2;
  case1.resize(n);
  case2.resize(n);
  dp[0] = 0;
  int prv = 0, cur = 0;
  long long sumB = 0;
  for(int i=1; i<=n; i++) {
    dp[i] = 1e16;
    if(i == 1) {
      cur = 1;
      sumB += all[1].first;
    }
    else {
      if(all[i].second != all[i-1].second) {
        prv = cur;
        cur = 1;
        // UPDATE ALL
        case1.range_assign(0, n, 0);
        case2.range_assign(0, n, 0);
        long long sumR = 0, cntR = 0;
        for(int j=i-1; j>=i-prv; j--) {
          sumR += all[j].first;
          cntR++;
          case1.range_add(j, j, dp[j-1] - sumR + cntR * all[i-1].first);
          case2.range_add(j, j, dp[j-1] - sumR + cntR * all[i].first);
        }
        sumB = all[i].first;
      }
      else {
        cur = cur + 1;
        sumB += all[i].first;
      }
    }
    if(prv == 0) continue;
    // prv, cur
    //cout << i << ": " << prv << " " << cur << "\n";
    // special case
    dp[i] = min(dp[i], dp[i - cur] + f(i-cur, i-cur, i-cur+1, i)); 

    long long cntB = cur;
    // case 1 prv <= cur
    // dp[i] = dp[j-1] + sumB - sumR + cntR * a[i-cur] - cntB * a[i-cur],  i-cur-prv+1 to i-cur
    dp[i] = min(dp[i], case1.query_min(i-cur-min(prv, cur) + 1, i-cur) + sumB - cntB * all[i-cur].first);

    // case 2 prv > cur
    // dp[i] = dp[j-1] + sumB - sumR + cntR * a[i-cur+1] - cntB * a[i-cur+1]
    if(prv > cur) dp[i] = min(dp[i], case2.query_min(i-cur-prv+1, i-cur-cur) + sumB - cntB * all[i-cur+1].first);

    /*
    bool active = 0;
    int cntsame = 0, cntdiff = 0;
    for(int j=i; j>=1; j--) {
      if(all[j].second == all[i].second && active) {
        break;
      }
      if(all[j].second == all[i].second) cntsame++;
      if(all[j].second != all[i].second) {
        active = 1; // use [j, i], reference dp[j-1]
        cntdiff++;
        dp[i] = min(dp[i], dp[j-1] + f(j, j+cntdiff-1, j+cntdiff, i));
        dp[i] = min(dp[i], dp[j] + f(j, j+cntdiff-1, j+cntdiff, i));
      }
    }
    */
  }

  //for(int i=1; i<=n; i++) cout << all[i].first << " \n"[i == n];
  //for(int i=1; i<=n; i++) cout << all[i].second << " \n"[i == n];
  //for(int i=1; i<=n; i++) cout << dp[i] << " \n"[i == n];
  return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:258:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |   for(int i=0; i<r.size(); i++) all.push_back({r[i], 'R'});
      |                ~^~~~~~~~~
wiring.cpp:259:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |   for(int i=0; i<b.size(); i++) all.push_back({b[i], 'B'});
      |                ~^~~~~~~~~

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