Submission #909594

#	Time	Username	Problem	Language	Result	Execution time	Memory
909594		rxlfd314	Meetings (IOI18_meetings)	C++17	19 / 100	477 ms	3088 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

vt<ll> Sub2(vt<int> H, vt<int> L, vt<int> R) {
  const int N = size(H), Q = size(L);
  vt<ll> ans(Q, LLONG_MAX);
  ll fdp[N], rdp[N];
  FOR(q, 0, Q-1) {
    int l = L[q], r = R[q];
    vt<int> sk;
    FOR(i, l, r) {
      while (size(sk) && H[sk.back()] <= H[i])
        sk.pop_back();
      fdp[i] = (size(sk) ? fdp[sk.back()] : 0ll) + 1ll * H[i] * (i - (size(sk) ? sk.back() : l-1));
      sk.push_back(i);
    }
    sk.clear();
    ROF(i, r, l) {
      while (size(sk) && H[sk.back()] <= H[i])
        sk.pop_back();
      rdp[i] = (size(sk) ? rdp[sk.back()] : 0ll) + 1ll * H[i] * ((size(sk) ? sk.back() : r+1) - i);
      ans[q] = min(ans[q], rdp[i] + fdp[i] - H[i]);
      sk.push_back(i);
    }
  }
  return ans;
}

struct ST {
  struct Node {
    int ans, p, s, len;
  };
  vt<Node> st;
  ST(vt<int> &A) {
    st.resize(size(A) << 2);
    build(A);
  }
  Node merge(Node a, Node b) {
    return {max({a.ans, b.ans, a.s + b.p}), a.p + (a.p == a.len) * b.p, b.s + (b.s == b.len) * a.s, a.len + b.len};
  }
  #define lc i << 1
  #define rc i << 1 | 1
  void build(vt<int> &A, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (tl == tr)
      st[i] = {A[i] < 2, A[i] < 2, A[i] < 2, 1};
    else {
      int tm = tl + tr >> 1;
      build(A, lc, tl, tm);
      build(A, rc, tm+1, tr);
      st[i] = merge(st[lc], st[rc]);
    }
  }
  Node qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (ql <= tl && tr <= qr)
      return st[i];
    if (tl > qr || tr < ql)
      return {0, 0, 0, 0};
    int tm = tl + tr >> 1;
    return merge(qry(ql, qr, lc, tl, tm), qry(ql, qr, rc, tm+1, tr));
  }
  #undef lc
  #undef rc
};

vt<ll> Sub3(vt<int> H, vt<int> L, vt<int> R) {
  const int Q = size(L);
  ST st(H);
  vt<ll> ans(Q);
  FOR(i, 0, Q-1) {
    int l = L[i], r = R[i];
    int v = st.qry(l, r).ans;
    ans[i] = v + 2 * (r - l + 1 - v);
  }
  return ans;
}

vt<ll> minimum_costs(vt<int> H, vt<int> L, vt<int> R) {
  const int N = size(H), Q = size(L);
  if (N <= 5000 && Q <= 5000)
    return Sub2(H, L, R);
  if (*max_element(all(H)) < 3)
    return Sub3(H, L, R);
}

Compilation message (stderr)

meetings.cpp: In member function 'void ST::build(std::vector<int>&, int, int, int)':
meetings.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
meetings.cpp: In member function 'ST::Node ST::qry(int, int, int, int, int)':
meetings.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
   98 | }
      | ^

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