Submission #282063

#	Time	Username	Problem	Language	Result	Execution time	Memory
282063		Haunted_Cpp	Meetings (IOI18_meetings)	C++17	36 / 100	776 ms	234876 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;


typedef long long i64;

const int MAX_N = 5e3 + 5;

const int VALID = 1;
const int INVALID = -1e9;

class SegmentTree {
private: 
  struct Node {
    int pre, suf, best, sum;
    Node() {
      pre = suf = best = sum = 0;
    }
    Node(int delta) {
      pre = suf = best = sum = delta;
    }
    void merge(Node l, Node r) {
      pre = max(l.pre, l.sum + r.pre);
      suf = max(r.suf, r.sum + l.suf);
      best = max({l.best, r.best, l.suf + r.pre});
      sum = l.sum + r.sum;
      pre = max(pre, INVALID);
      suf = max(suf, INVALID);
      best = max(best, INVALID);
      sum = max(sum, INVALID);
    }
  };
  const int LO, HI;
  vector<Node> seg;
  void build(int l, int r, int node, const vector<int> &arr) {
    if (l == r) {
      seg[node] = (arr[l] == 1 ? Node(VALID) : Node(INVALID));
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  Node range_query(int ql, int qr, int l, int r, int node) {
    if (l > qr || r < ql) return Node(INVALID);
    if (l >= ql && r <= qr) return seg[node];
    const int mid = l + (r - l) / 2;
    Node esq = range_query(ql, qr, l, mid, 2 * node + 1);
    Node dir = range_query(ql, qr, mid + 1, r, 2 * node + 2);
    Node ans;
    ans.merge(esq, dir);
    return ans;
  }
public:
  SegmentTree(const vector<int> &arr) : LO(0), HI((int)arr.size() - 1) {
    seg.clear();
    seg.resize(4 * (int) arr.size());
    build(LO, HI, 0, arr);
  }
  int range_query(int ql, int qr) {
    Node ans = range_query(ql, qr, LO, HI, 0);
    return max(0, ans.best);
  }
};

i64 r[MAX_N][MAX_N];
i64 l[MAX_N][MAX_N];



vector<i64> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  const int n = H.size();
  const int q = L.size();
  vector<i64> C(q);
  if (n <= 5000) {
    for (int i = 0; i < n; i++) {
      int mx;
      mx = H[i];
      for (int j = i + 1; j < n; j++) {
        mx = max(mx, H[j]);
        r[i][j] = r[i][j - 1] + mx;
      }
      mx = H[i];
      l[i][i] = mx;
      for (int j = i - 1; ~j; j--) {
        mx = max(mx, H[j]);
        l[i][j] = l[i][j + 1] + mx;
      }
    }
    for (int i = 0; i < q; i++) {
      const int lo = L[i];
      const int hi = R[i];
      i64 mn = 1e18;
      for (int j = lo; j <= hi; j++) {
        i64 left_side = l[j][lo];
        i64 right_side = r[j][hi];
        mn = min(mn, left_side + right_side);
      }
      C[i] = mn;
    }
  } else {
    SegmentTree seg(H);
    for (int i = 0; i < q; i++) {
      const int lo = L[i];
      const int hi = R[i];
      C[i] = (hi - lo + 1) * 2 - seg.range_query(lo, hi);
    }
  }
  return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40