이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
컴파일 시 표준 에러 (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 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |