oj.uz

Submission #282063

# Submission time Handle Problem Language Result Execution time Memory
282063 2020-08-23T23:12:21 Z Haunted_Cpp Meetings (IOI18_meetings) C++17
36 / 100
 776 ms 234876 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 78 ms 95140 KB Output is correct
3 Correct 77 ms 95096 KB Output is correct
4 Correct 84 ms 95096 KB Output is correct
5 Correct 81 ms 95072 KB Output is correct
6 Correct 79 ms 95096 KB Output is correct
7 Correct 76 ms 95148 KB Output is correct
8 Correct 81 ms 95096 KB Output is correct
9 Correct 79 ms 95096 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 78 ms 95140 KB Output is correct
3 Correct 77 ms 95096 KB Output is correct
4 Correct 84 ms 95096 KB Output is correct
5 Correct 81 ms 95072 KB Output is correct
6 Correct 79 ms 95096 KB Output is correct
7 Correct 76 ms 95148 KB Output is correct
8 Correct 81 ms 95096 KB Output is correct
9 Correct 79 ms 95096 KB Output is correct
10 Correct 380 ms 234744 KB Output is correct
11 Correct 747 ms 234672 KB Output is correct
12 Correct 381 ms 234876 KB Output is correct
13 Correct 776 ms 234744 KB Output is correct
14 Correct 388 ms 234740 KB Output is correct
15 Correct 377 ms 234744 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 41 ms 2688 KB Output is correct
3 Correct 129 ms 11768 KB Output is correct
4 Correct 127 ms 11768 KB Output is correct
5 Correct 101 ms 12028 KB Output is correct
6 Correct 114 ms 11768 KB Output is correct
7 Correct 121 ms 11768 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 41 ms 2688 KB Output is correct
3 Correct 129 ms 11768 KB Output is correct
4 Correct 127 ms 11768 KB Output is correct
5 Correct 101 ms 12028 KB Output is correct
6 Correct 114 ms 11768 KB Output is correct
7 Correct 121 ms 11768 KB Output is correct
8 Incorrect 124 ms 11664 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 78 ms 95140 KB Output is correct
3 Correct 77 ms 95096 KB Output is correct
4 Correct 84 ms 95096 KB Output is correct
5 Correct 81 ms 95072 KB Output is correct
6 Correct 79 ms 95096 KB Output is correct
7 Correct 76 ms 95148 KB Output is correct
8 Correct 81 ms 95096 KB Output is correct
9 Correct 79 ms 95096 KB Output is correct
10 Correct 380 ms 234744 KB Output is correct
11 Correct 747 ms 234672 KB Output is correct
12 Correct 381 ms 234876 KB Output is correct
13 Correct 776 ms 234744 KB Output is correct
14 Correct 388 ms 234740 KB Output is correct
15 Correct 377 ms 234744 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 41 ms 2688 KB Output is correct
18 Correct 129 ms 11768 KB Output is correct
19 Correct 127 ms 11768 KB Output is correct
20 Correct 101 ms 12028 KB Output is correct
21 Correct 114 ms 11768 KB Output is correct
22 Correct 121 ms 11768 KB Output is correct
23 Incorrect 124 ms 11664 KB Output isn't correct
24 Halted 0 ms 0 KB -