# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
425202 | Tangent | 모임들 (IOI18_meetings) | C++17 | 81 ms | 4532 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int N = H.size();
vpii segments;
vii segment(N);
rep(i, N) {
if (H[i] == 1) {
if (i && H[i - 1] == 1) {
segments.back().second++;
} else {
segments.emplace_back(i, i + 1);
}
segment[i] = segments.size() - 1;
} else {
segment[i] = segments.size();
}
}
vii t(2 * segments.size());
rep(i, segments.size()) {
t[segments.size() + i] = segments[i].second - segments[i].first;
}
for (int i = segments.size() - 1; i > 0; i--) {
t[i] = max(t[i * 2], t[i * 2 + 1]);
}
vll res(Q);
rep(i, Q) {
int best = 0;
int l, r;
if (H[L[i]] == 1) {
best = max(best, min(R[i] + 1, segments[segment[L[i]]].second) - L[i]);
l = segment[L[i]] + 1;
} else {
l = segment[L[i]];
}
if (H[R[i]] == 1) {
best = max(best, R[i] - max(L[i], segments[segment[R[i]]].first) + 1);
r = segment[R[i]];
} else {
r = segment[R[i]];
}
if (l < r) {
l += segments.size();
r += segments.size();
int curr = 0;
while (l < r) {
if (l % 2) {
curr = max(curr, t[l++]);
}
if (r % 2) {
curr = max(curr, t[--r]);
}
l /= 2;
r /= 2;
}
best = max(best, curr);
}
res[i] = (R[i] - L[i] + 1) * 2 - best;
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |