이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
vector<vector<ll> > tree(400005, vector<ll>(3));
vector<int> h;
void build(int indx, int st, int end) {
if (st == end) {
if (h[st] == 1)
tree[indx] = {1, 1, 1};
else
tree[indx] = {0, 0, 0};
return;
}
int mid = (st + end) / 2;
build(indx*2, st, mid);
build(indx*2+1, mid+1, end);
if (tree[indx*2][2] == mid-st+1)
tree[indx][2] = tree[indx*2][2] + tree[indx*2+1][2];
else
tree[indx][2] = tree[indx*2][2];
if (tree[indx*2+1][0] == end-mid)
tree[indx][0] = tree[indx*2][0] + tree[indx*2+1][0];
else
tree[indx][0] = tree[indx*2][0];
tree[indx][1] = max(max(tree[indx*2][1], tree[indx*2+1][1]), max(tree[indx][0], tree[indx][2]));
tree[indx][1] = max(tree[indx][1], tree[indx*2][2]+tree[indx*2+1][0]);
}
vector<ll> query(int indx, int st, int end, int l, int r) {
if (st > r || end < l)
return {0, 0, 0};
if (l <= st && end <= r)
return tree[indx];
int mid = (st + end) / 2;
vector<ll> left = query(indx*2, st, mid, l, r);
vector<ll> right = query(indx*2+1, mid+1, end, l, r);
vector<ll> ans(3);
if (left[2] == mid-st+1)
ans[2] = left[2] + right[2];
else
ans[2] = left[2];
if (right[0] == end-mid)
ans[0] = left[0] + right[0];
else
ans[0] = left[0];
ans[1] = max(max(left[1], right[1]), max(ans[0], ans[2]));
ans[1] = max(ans[1], left[2]+right[0]);
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = H.size(), mx, Q = L.size();
h = H;
build (1, 0, n-1);
vector<long long> ans(Q);
for (int q = 0; q < Q; q++) {
// vector<ll> ret = query(1, 0, n-1, L[q], R[q]);
// cout << ret[0] << ' ' << ret[1] << ' ' << ret[2] << '\n';
ans[q] = (R[q]-L[q]+1)*2 - query(1, 0, n-1, L[q], R[q])[1];
}
return ans;
}
/*
3 3
2 1 2
0 0
0 1
0 2
*/
컴파일 시 표준 에러 (stderr) 메시지
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:70:21: warning: unused variable 'mx' [-Wunused-variable]
70 | int n = H.size(), mx, Q = L.size();
| ^~
# | 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... |