QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #507272 | #5500. Bars | NYCU_MyGO# | AC ✓ | 204ms | 11752kb | C++20 | 6.3kb | 2024-08-06 15:02:34 | 2024-08-06 15:02:34 |
Judging History
answer
#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO
void solve() {
int N; cin >> N;
vector<int> P(N);
for (int &x : P) cin >> x;
vector<int> pick(N, 0);
{
deque<int> deq{0};
for (int i = 1; i < N; ++i) {
if (P[i] <= P[deq[0]]) continue;
while (SZ(deq) >= 2) {
int gain = (i - deq[0]) * (P[deq[0]] - P[deq[1]]);
int loss = (deq[0] - deq[1]) * (P[i] - P[deq[0]]);
if (gain <= loss) deq.pf();
else break;
}
deq.ef(i);
}
for (int x : deq) pick[x] = 1;
}
{
deque<int> deq{N-1};
for (int i = N-2; i >= 0; --i) {
if (P[i] <= P[deq[0]]) continue;
while (SZ(deq) >= 2) {
int gain = (deq[0] - i) * (P[deq[0]] - P[deq[1]]);
int loss = (deq[1] - deq[0]) * (P[i] - P[deq[0]]);
if (gain <= loss) deq.pf();
else break;
}
deq.ef(i);
}
for (int x : deq) pick[x] = 1;
}
int ans = 0;
for (int i = 0, left = 0; i < N; ++i) {
ans += left;
if (pick[i]) left = P[i];
}
for (int i = N-1, right = 0; i >= 0; --i) {
ans += right;
if (pick[i]) right = P[i];
}
cout << ans << "\n";
}
int32_t main() {
fastIO();
int t = 1; cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
fprintf(stderr, "\u001b[33m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
2 4 5 2 2 6 5 1 5 4 4 1
output:
33 29
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 195ms
memory: 3708kb
input:
10000 4 5 2 2 6 5 1 5 4 4 1 197 763787596 15221694 898228999 187472305 466351873 822742732 437754202 800092772 843092246 915675776 166265020 346340615 796714085 497548541 182089610 64356048 363276768 181268733 257949015 236568898 752096761 928725929 443146784 114577469 833053207 38120723 14891030 41...
output:
33 29 382465638565 663641330002 550288673161 458946673513 296420749955 875760099157 632854843886 586309163102 225238173690 716890380495 466644027129 283505446030 585094154153 201707398762 336548832140 483300272586 606382970973 587469399170 408018096564 827347820764 975377092201 925120038848 26408806...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 188ms
memory: 11048kb
input:
6 500000 287001636 204980186 997392401 188445265 873977784 672984447 520446063 460936121 420229946 413937980 95267858 869951831 87353679 843288346 375704325 376217775 66621398 502675506 854835633 99408891 880520553 944446461 690146628 632137514 179514334 551490018 981073461 196185611 719601446 93667...
output:
999978185027008 499999063998982 999946405821678 999970304287364 499999737998030 999979204653771
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 185ms
memory: 11248kb
input:
6 500000 669619127 356830845 494606145 526755381 169647973 602343819 658032437 326960015 207942215 173060393 217232953 314912605 366676785 510103533 489446303 121223259 374781515 484954847 134957195 400053837 122117455 627813351 583524019 624468283 613073257 263488687 242182189 527854337 554306009 1...
output:
953660650057664 883167999492927 499223754839723 667315106896885 904445177106028 879334018232172
result:
ok 6 lines
Test #5:
score: 0
Accepted
time: 204ms
memory: 11752kb
input:
6 500000 12403960 2930024 1808469 4773510 8417429 6369605 2751412 4062450 9895452 9966727 11476617 4854207 2807239 9516332 5730691 731629 2368916 1351133 1435333 6860794 5460899 2506776 7936802 12585522 8631641 3397564 316192 11362360 10913499 5967508 7437490 12648666 5703570 637890 7908197 361480 8...
output:
667267911235251 678790984141243 666630987914525 671493601773996 717382005630376 667971386351316
result:
ok 6 lines