Submission #1247192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247192		EJOI2019Andrew	Catfish Farm (IOI22_fish)	C++20	6 / 100	1071 ms	131788 KiB

fish

#include "fish.h"

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const ll INF = 1LL << 60;

class SegTree {
public:
  vector<ll> tree;
  int n;
  SegTree(int _n) : n(_n), tree(4 * _n, -INF) {}
  void update(int idx, ll val) {
    update(1, 0, n - 1, idx, val);
  }
  ll query(int left, int right) {
    if (left > right) return -INF;
    return query(1, 0, n - 1, left, right);
  }
private:
  void update(int node, int s, int e, int idx, ll val) {
    if (s == e) {
      tree[node] = val;
      return;
    }
    int m = (s + e) / 2;
    if (idx <= m) update(2 * node, s, m, idx, val);
    else update(2 * node + 1, m + 1, e, idx, val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
  }
  ll query(int node, int s, int e, int left, int right) {
    if (right < s || e < left) return -INF;
    if (left <= s && e <= right) return tree[node];
    int m = (s + e) / 2;
    return max(query(2 * node, s, m, left, right), query(2 * node + 1, m + 1, e, left, right));
  }
};

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  vector<vector<pair<int, ll>>> fish(N);
  for (int i = 0; i < M; i++) {
    fish[X[i]].push_back({Y[i], W[i]});
  }
  vector<vector<int>> possible(N);
  for (int i = 0; i < M; i++) {
    int col = X[i];
    int thresh = Y[i] + 1;
    possible[col].push_back(thresh);
    if (col - 1 >= 0) possible[col - 1].push_back(thresh);
    if (col + 1 < N) possible[col + 1].push_back(thresh);
  }
  for (int c = 0; c < N; c++) {
    possible[c].push_back(0);
    sort(possible[c].begin(), possible[c].end());
    auto it = unique(possible[c].begin(), possible[c].end());
    possible[c].resize(it - possible[c].begin());
  }
  vector<int> global_y(M + N + 2);
  vector<ll> global_sum(M + N + 2);
  vector<int> inn(N);
  vector<int> outt(N);
  int cnt = 0;
  for (int c = 0; c < N; c++) {
    auto &p = fish[c];
    p.push_back({N, 0});
    sort(p.begin(), p.end());
    int sz = p.size();
    ++cnt;
    global_y[cnt] = p[0].first + 1;
    global_sum[cnt] = p[0].second;
    inn[c] = cnt;
    for (int j = 1; j < sz; j++) {
      ++cnt;
      global_y[cnt] = p[j].first + 1;
      global_sum[cnt] = global_sum[cnt - 1] + p[j].second;
    }
    outt[c] = cnt;
  }
  auto get_sum_le = [&](int col, int val) -> ll {
    if (val < 0) return 0;
    if (col < 0 || col >= N) return 0;
    int l = inn[col], r = outt[col];
    auto it = upper_bound(global_y.begin() + l, global_y.begin() + r + 1, val + 1);
    int k = it - global_y.begin() - 1;
    if (k < l) return 0;
    return global_sum[k];
  };
  auto get_sum_range = [&](int col, int low, int high) -> ll {
    if (low > high) return 0;
    return get_sum_le(col, high) - get_sum_le(col, low - 1);
  };
  vector<vector<ll>> dp_inc(N + 1);
  vector<vector<ll>> dp_dec(N + 1);
  vector<map<int, ll>> closed_map(N + 1);
  closed_map[0][0] = 0;
  for (int i = 0; i < N; i++) {
    vector<int> Hcur = possible[i];
    int s = Hcur.size();
    vector<ll> new_inc(s, -INF);
    vector<ll> new_dec(s, -INF);
    map<int, ll> new_closed;
    vector<int> Hprev = (i == 0 ? vector<int>{0} : possible[i - 1]);
    vector<ll> prev_inc = (i == 0 ? vector<ll>{0} : dp_inc[i]);
    vector<ll> prev_dec = (i == 0 ? vector<ll>{-INF} : dp_dec[i]);
    int t = Hprev.size();
    int j0 = lower_bound(Hcur.begin(), Hcur.end(), 0) - Hcur.begin();
    if (j0 == s || Hcur[j0] != 0) j0 = -1;
    // from prev_inc
    {
      SegTree st(t);
      for (int j = 0; j < t; j++) {
        ll val = prev_inc[j] + get_sum_le(i, Hprev[j] - 1) - get_sum_le(i - 1, Hprev[j] - 1);
        st.update(j, val);
      }
      for (int k = 0; k < s; k++) {
        ll h = Hcur[k];
        ll const_k = -get_sum_le(i, h - 1) + get_sum_le(i - 1, h - 1);
        int pos = upper_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin() - 1;
        ll mx = st.query(0, pos);
        if (mx > -INF) new_inc[k] = max(new_inc[k], mx + const_k);
        int pos2 = lower_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin();
        mx = st.query(pos2, t - 1);
        if (mx > -INF) new_dec[k] = max(new_dec[k], mx + const_k);
      }
    }
    // from prev_dec
    {
      SegTree st(t);
      for (int j = 0; j < t; j++) {
        ll val = prev_dec[j] + get_sum_le(i, Hprev[j] - 1);
        st.update(j, val);
      }
      for (int k = 0; k < s; k++) {
        ll h = Hcur[k];
        ll const_k = -get_sum_le(i, h - 1);
        // skip for new_inc
        int pos2 = lower_bound(Hprev.begin(), Hprev.end(), h) - Hprev.begin();
        ll mx = st.query(pos2, t - 1);
        if (mx > -INF) new_dec[k] = max(new_dec[k], mx + const_k);
      }
    }
    // from closed_map[i] to new_inc and new_closed
    ll val0 = closed_map[i][0];
    if (val0 > -INF) {
      for (int k = 0; k < s; k++) {
        ll h = Hcur[k];
        if (h == 0) continue;
        ll rsum = get_sum_range(i - 1, 0, h - 1);
        ll lsum = get_sum_range(i, h, 0 - 1);
        new_inc[k] = max(new_inc[k], val0 + rsum + lsum);
      }
    }
    ll maxv = -INF;
    for (auto &p : closed_map[i]) {
      maxv = max(maxv, p.second);
    }
    if (j0 >= 0 && maxv > -INF) {
      ll value = maxv + get_sum_range(i, 0, 0 - 1) + 0;
      new_closed[0] = max(new_closed[0], value);
    }
    // update new_closed from prev_inc and prev_dec
    if (j0 >= 0) {
      for (int j = 0; j < t; j++) {
        if (prev_inc[j] == -INF) continue;
        ll value = prev_inc[j] + get_sum_range(i, 0, Hprev[j] - 1) + 0;
        int h_before = Hprev[j];
        new_closed[h_before] = max(new_closed[h_before], value);
      }
      for (int j = 0; j < t; j++) {
        if (prev_dec[j] == -INF) continue;
        ll value = prev_dec[j] + get_sum_range(i, 0, Hprev[j] - 1) + 0;
        int h_before = Hprev[j];
        new_closed[h_before] = max(new_closed[h_before], value);
      }
    }
    dp_inc[i + 1] = new_inc;
    dp_dec[i + 1] = new_dec;
    closed_map[i + 1] = new_closed;
  }
  ll ans = 0;
  for (auto v : dp_inc[N]) ans = max(ans, v);
  for (auto v : dp_dec[N]) ans = max(ans, v);
  for (auto &p : closed_map[N]) ans = max(ans, p.second);
  return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16