Submission #1239311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239311		madamadam3	Nile (IOI24_nile)	C++20	0 / 100	173 ms	20000 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

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;

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

    st.resize(4*n);
    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));
  }

  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];

    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 k, ll v) {
    if (!(l <= k && k < r)) return st[i];
    if (l + 1 == r) return st[i] = Node(v, k);

    int m = l + (r - l) / 2;
    return st[i] = Node(update(2*i+1, l, m, k, v), update(2*i+2, m, r, k, 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, v);
  }
};

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

  auto rmq = RMQ(n, b);

  vl R(q, 0);
  FOR(qn, 0, q) {
    rmq = RMQ(n, b);

    FOR(i, 0, n) {
      if (rmq.query(i, i+1).best == INF) continue;
      auto best = rmq.query(i+1, i+E[qn]+1);
      if (best.best == INF) {
        R[qn] += a[i];
        // cout << i << " had to go alone\n";
      } else {
        R[qn] += b[i] + best.best;
        rmq.update(best.idx, INF);
        rmq.update(i, INF);
        // cout << "best for " << i << " is " << best.idx << " with cost " << b[i] + best.best << "\n";
      }
    }
  }
  return R;
}

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