이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
const int mxN = 75e4;
const int offset = 2<<__lg(mxN-1);
struct S {
int w = 0, l = 0, m = 0, r = 0;
void pull(S a, S b) {
w = a.w + b.w;
l = (a.l == a.w ? a.l+b.l : a.l);
m = max({a.m, a.r + b.l, b.m});
r = (b.r == b.w ? b.r+a.r : b.r);
}
};
S st[2*offset];
S qry(int i, int j) {
i += offset-1;
j += offset+1;
S l, r;
while (i+1 < j) {
if (i%2 == 0) st[i+1].pull(st[2*(i+1)], st[2*(i+1)+1]);
if (j%2 == 0) st[j-1].pull(st[2*(j-1)], st[2*(j-1)+1]);
i /= 2, j /= 2;
}
l.pull(l, r);
return l;
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int n = (int)h.size();
int q = (int)l.size();
vector<ll> ans(q);
for (int i = 0; i < n; ++i) {
assert(h[i] == 0 || h[i] == 1);
st[offset+i].w = 1;
if (h[i] == 0)
st[offset+i].l = st[offset+i].m = st[offset+i].r = 1;
}
for (int i = offset-1; i > 0; --i)
st[i].pull(st[2*i], st[2*i+1]);
for (int qq = 0; qq < q; ++qq)
ans[qq] = qry(l[qq], r[qq]).w;
return ans;
}
# | 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... |