| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 612121 | M_W | 모임들 (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstdlib>
#include <vector>
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
#include <bits/stdc++.h>
#define ii pair<long long, long long>
using namespace std;
long long t[750001 << 2];
vector<int> H;
int last = 0, N;
vector<ii> Q[750001];
long long query(int v, int tl, int tr, int l, int r){
if(l > r) return -1;
if(tl == l && tr == r) return t[v];
int tm = (tl + tr) >> 1;
return max(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
void ins(int v, int tl, int tr, int pos, int val){
if(tl == pos && tr == pos){
t[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) ins(v * 2, tl, tm, pos, val);
else ins(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
vector<long long> minimum_costs(vector<int> H_tmp, vector<int> L, vector<int> R){
H = H_tmp; N = H.size();
for(int i = 0; i < L.size(); i++) Q[R[i]].push_back({L[i], i});
vector<long long> ans(200001);
for(int i = 0; i < N; i++){
if(H[i] == 2){
ins(1, 0, N, last, i - last);
last = i + 1;
}
for(auto x : Q[i]){
long long val = query(1, 0, N, x.first + 1, i + 1);
val = max(val, ((i - max(last * 1ll, (x.first + 1) * 1ll)) * 1ll) + (H[i] == 2 ? 0 : 1ll));
// printf(">> %d %lld\n", i - x.first + 1, val);
ans[x.second] = ((i - x.first + 1 - val) * 2ll) + (val * 1ll);
}
}
ans.resize(L.size());
return ans;
}
int main() {
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}