Submission #1239882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239882		madamadam3	Nile (IOI24_nile)	C++20	32 / 100	61 ms	9404 KiB

nile

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

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pi = pair<int, int>;
using vpi = vector<pi>;

#define sz(x) int((x).size())
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define trace(x) for (auto &el : x) cout << el << " "
#define each(a, x) for (auto &a : x)

const ll INF = 1e18;

struct Node {
  ll best; int idx;

  Node() : best(INF), idx(-1) {};
  Node(ll v, int i) : best(v), idx(i) {};
  Node(Node left, Node right) {
    best = min(left.best, right.best);
    if (left.best < right.best) idx = left.idx;
    else idx = right.idx;
  }
};

struct RMQ {
  int n; vl arr; vector<Node> st;
  vl lazy;

  RMQ() {};
  RMQ(int N, vl Arr) {
    n = N; arr = Arr;

    st.resize(4*n);
    lazy.assign(4*n, 0);
    build(0, 0, n);
  }

  Node build(int i, int l, int r) {
    if (l + 1 == r) return st[i] = Node(arr[l], l);

    int m = l + (r - l) / 2;
    return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
  }

  void apply(int i, ll update) {
    lazy[i] += update;
    st[i].best += update;
  }

  void push_down(int i) {
    apply(2*i+1, lazy[i]);
    apply(2*i+2, lazy[i]);

    lazy[i] = 0;
  }

  Node query(int i, int l, int r, int ql, int qr) {
    if (r <= ql || qr <= l) return Node();
    if (ql <= l && r <= qr) return st[i];

    push_down(i);
    int m = l + (r - l) / 2;
    return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
  }

  Node update(int i, int l, int r, int ql, int qr, ll v) {
    if (r <= ql || qr <= l) return st[i];
    if (ql <= l && r <= qr) {
      apply(i, v);
      return st[i];
    }

    push_down(i);
    int m = l + (r - l) / 2;
    return st[i] = Node(update(2*i+1, l, m, ql, qr, v), update(2*i+2, m, r, ql, qr, v));
  }

  Node query(int l, int r) {
    return query(0, 0, n, l, r);
  }

  void update(int k, ll v) {
    update(0, 0, n, k, k+1, v);
  }

  void update(int l, int r, ll v) {
    update(0, 0, n, l, r, v);
  }
};

struct DSU {
  int n;
  vector<int> par, size;

  DSU(int N) {
    n = N; par.assign(n, 0); iota(par.begin(), par.end(), 0); size.assign(n, 1); 
  }

  int find(int v) {
    if (par[v] == v) return v;
    return par[v] = find(par[v]);
  }

  void unite(int a, int b, ll &pairs) {
    a = find(a), b = find(b);
    if (a != b) {
      if (size[a] < size[b]) swap(a, b); 
      pairs -= (size[a] / 2) + (size[b] / 2);
      par[b] = a; size[a] += size[b];
      pairs += size[a] / 2;
    }
  }
};

void super_brute(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
  FOR(qn, 0, q) {
    vi perm(n); iota(all(perm), 0);
    ll best = INF;
    vi best_perm;

    do {
      ll cur = 0;
      bool is_b = true;
      for (int i = 0; i < n; i++) {
        if (is_b && i < n - 1 && abs(w[perm[i]] - w[perm[i+1]]) <= e[qn]) {
          cur += b[perm[i]] + b[perm[i+1]];
          i++;
        } else {
          is_b = false;
          cur += a[perm[i]];
        }
      }
      
      if (cur < best) {
        best = cur;
        best_perm = perm;
      }
    } while (next_permutation(all(perm)));

    answers[qn] = best;
    cout << "E[i]: " << e[qn] << " answers[qn]: " << answers[qn] << "\n";
    trace(best_perm); cout << "\n";
  }
}

void ab12(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
  vpi edges; FOR(i, 0, n-1) edges.pb({w[i+1] - w[i], i}); srt(edges);
  auto dsu = DSU(n);

  ll pairs = 0;
  int cur_edge = 0;

  FOR(qn, 0, q) {
    while (cur_edge < edges.size() && edges[cur_edge].first <= e[qn]) {
      pi edge = edges[cur_edge];
      ll weight = edge.first;
      int u = edge.second, v = edge.second + 1;

      dsu.unite(u, v, pairs);
      cur_edge++;
    }

    answers[qn] = 2 * n - 2 * pairs;
  }
}

void linedup(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
  FOR(qn, 0, q) {
    answers[qn] = accumulate(all(b), 0LL);
    vl ab(n); FOR(i, 0, n) ab[i] = a[i] - b[i];
    auto rmq = RMQ(n, ab);

    if (n % 2 == 1 && e[qn] == 1) {
      vl DP(n+1, INF);
      DP[0] = 0;

      FOR(i, 0, n) {
        DP[i+1] = min(DP[i+1], DP[i] + a[i]);
        if (i > 0) {
          DP[i+1] = min(DP[i+1], DP[i-1] + b[i-1] + b[i]);
        }
      }

      answers[qn] = DP[n];
    } else if (n%2==1) {
      answers[qn] += rmq.query(0, n).best;
    }
  }
}

void weirdp(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
  FOR(qn, 0, q) {
    ll best = INF;
    vl DP(n+1, INF);
    DP[0] = 0;
    auto rmq = RMQ(n, vl(n, INF));

    FOR(i, 0, n) {
      DP[i+1] = DP[i] + a[i];

      int pos = ub(bg(w), bg(w) + i, w[i] - e[qn] - 1) - bg(w);
      ll qbest = b[i] + rmq.query(pos, i).best;
      DP[i+1] = min(DP[i+1], qbest);

      rmq.update(0, i, a[i]);
      rmq.update(i, (DP[i] + b[i]) - rmq.query(i, i+1).best);
    }

    best = DP.back();
    answers[qn] = best;
  }
}

vl calculate_costs(vi W, vi A, vi B, vi E) {
  int n = sz(W), q = sz(E);
  vl w(all(W)), a(all(A)), b(all(B)), e(all(E)); srt(e);
  vi indices(n); iota(all(indices), 0); sort(all(indices), [&](int i, int j) {return w[i] < w[j];});
  FOR(i, 0, n) w[i] = W[indices[i]], a[i] = A[indices[i]], b[i] = B[indices[i]];

  vl answers(q, 0);
  // super_brute(n, q, a, b, w, e, answers);
  ab12(n, q, a, b, w, e, answers);
  // linedup(n, q, a, b, w, e, answers);
  // weirdp(n, q, a, b, w, e, answers);

  vl R(q, 0); FOR(i, 0, q) R[i] = answers[lb(all(e), E[i]) - bg(e)];
  return R;
}

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