# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1127518 | duong3982 | Candies (JOI18_candies) | C++20 | 104 ms | 10024 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left___
#define right ___right___
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 2e5 + 5;
int n, k;
int lab[N], lt[N], rt[N], a[N];
bool del[N];
long long val[N];
int find(int u) {
assert(u);
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
void mrg(int u, int v) {
if ((u = find(u)) == (v = find(v))) {
return;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
lab[u] += lab[v];
lab[v] = u;
del[u] |= del[v];
lt[u] = min(lt[u], lt[v]);
rt[u] = max(rt[u], rt[v]);
}
int getL(int i) {
return lt[find(i)];
}
int getR(int i) {
return rt[find(i)];
}
long long qryVal(int i) {
return val[find(i)];
}
void process(void) {
cin >> n;
using T = tuple<long long, int, int>;
priority_queue<T> pq;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
lab[i] = -1;
val[i] = a[i];
lt[i] = rt[i] = i;
pq.push({val[i], i, i});
}
long long res = 0;
for (int i = 0; i < (n + 1) / 2; ++i) {
while (1) {
assert(pq.size());
long long x;
int l, r;
tie(x, l, r) = pq.top();
pq.pop();
if (l ^ getL(l) || r ^ getR(r)) {
continue;
}
del[find(l)] |= l == 1 || r == n;
res += x;
long long nxt = -qryVal(l);
if (l > 1) {
nxt += qryVal(l - 1);
mrg(l, l - 1);
}
if (r < n) {
nxt += qryVal(r + 1);
mrg(r, r + 1);
}
int id = find(l);
if (!del[id]) {
val[id] = nxt;
pq.push({val[id], lt[id], rt[id]});
}
break;
}
cout << res << "\n";
}
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
file("DAN");
// int t; cin >> t; while (t--)
process();
return (0^0);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |