Submission #909594

# Submission time Handle Problem Language Result Execution time Memory
909594 2024-01-17T09:38:46 Z rxlfd314 Meetings (IOI18_meetings) C++17
19 / 100
477 ms 3088 KB
#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

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 | }
      | ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 476 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 476 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 128 ms 820 KB Output is correct
11 Correct 472 ms 804 KB Output is correct
12 Correct 127 ms 820 KB Output is correct
13 Correct 477 ms 812 KB Output is correct
14 Correct 61 ms 852 KB Output is correct
15 Correct 63 ms 848 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 23 ms 3088 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 23 ms 3088 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 476 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 128 ms 820 KB Output is correct
11 Correct 472 ms 804 KB Output is correct
12 Correct 127 ms 820 KB Output is correct
13 Correct 477 ms 812 KB Output is correct
14 Correct 61 ms 852 KB Output is correct
15 Correct 63 ms 848 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Incorrect 23 ms 3088 KB Output isn't correct
18 Halted 0 ms 0 KB -