이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Seg {
struct Node {
int l, r, tot, sz;
static Node join(Node const& a, Node const& b) {
Node ans = {a.l,
b.r,
max({a.tot, b.tot, a.r+b.l}),
a.sz + b.sz};
if (a.tot == a.sz) ans.l = a.tot + b.l;
if (b.tot == b.sz) ans.r = b.tot + a.r;
return ans;
}
};
vector<Node> tree;
vector<int> const& v;
Seg(vector<int> const& v) : tree(v.size()*4), v(v) {
build(0, 0, v.size()-1);
}
void build(int no, int l, int r) {
if (l == r) {
if (v[l] == 1) tree[no] = Node{1, 1, 1, 1};
else tree[no] = Node{0, 0, 0, 1};
}
else {
int m = (l+r)/2;
build(no*2+1, l, m);
build(no*2+2, m+1, r);
tree[no] = Node::join(tree[no*2+1], tree[no*2+2]);
}
}
Node get(int no, int l, int r, int a, int b) {
if (a <= l and r <= b) return tree[no];
else {
int m = (l+r)/2;
if (b <= m) return get(no*2+1, l, m, a, b);
if (a > m) return get(no*2+2, m+1, r, a, b);
return Node::join(get(no*2+1, l, m, a, b),
get(no*2+2, m+1, r, a, b));
}
}
};
vector<ll> minimum_costs(vector<int> h, vector<int> L,
vector<int> R) {
int n = h.size();
Seg sg(h);
int q = L.size();
vector<ll> res;
for (int at = 0; at < q; at++) {
int l = L[at], r = R[at];
Seg::Node ans = sg.get(0, 0, n-1, l, r);
res.push_back(2ll*(r-l+1) - ans.tot);
}
return res;
}
# | 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... |