Submission #1239827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239827		madamadam3	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	19528 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>;

#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);
  }
};

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) {
  FOR(qn, 0, q) {
    ll cur = 0;
    FOR(i, 0, n) {
      if (i < n - 1 && w[i+1] - w[i] <= e[qn]) {
        cur += b[i] + b[i+1];
        i++;
      } else {
        cur += a[i];
      }
    }

    answers[qn] = cur;
  }
}

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: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18