QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246462 | #7079. Array | yyz | WA | 233ms | 3864kb | C++14 | 2.5kb | 2023-11-10 20:40:48 | 2023-11-10 20:40:49 |
Judging History
answer
#include <bits/stdc++.h>
#define V vector
#define Vi vector<int>
#define sz(a) ((int)a.size())
#define fi first
#define se second
#define Int pair<int, int>
#define Inf ((int)1e18)
#define pb push_back
#define ins insert
#define For(i, x, y) for (int i = (x); i <= (y); i++)
#define Rep(i, x, y) for (int i = (x); i >= (y); i--)
#define seg int p, int l, int r
#define lid p << 1, l, mid
#define all(a) a.begin(), a.end()
#define rid p << 1 | 1, mid + 1, r
#define mid ((l + r) / 2)
#define Ceil(x, y) ((x + y - 1) / y)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
using namespace std;
#define int long long
struct Ace_taffy {
Ace_taffy(int n) : mn(4 * n + 5, Inf) {}
void add(seg, int x, int z) {
if (l == r) {
mn[p] = z;
return;
}
x <= mid ? add(lid, x, z) : add(rid, x, z);
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}
int ask(seg, int L, int R) {
if (L > R) return Inf;
if (l >= L && r <= R) return mn[p];
return min(L <= mid ? ask(lid, L, R) : Inf, R > mid ? ask(rid, L, R) : Inf);
}
Vi mn;
};
signed main() {
#ifndef ONLINE_JUDGE
IO(1);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _, n;
for (cin >> _; cin >> n;) {
Vi a(n + 5);
For(i, 1, n) cin >> a[i];
map<int, int> mp;
Vi las(n + 5);
Rep(i, n, 1) {
las[i] = mp.count(a[i]) ? mp[a[i]] : n + 1;
mp[a[i]] = i;
}
auto calc = [&](int l, int r) { return (l + r) * (r - l + 1) / 2; };
mp.clear();
Vi vec;
int sum = 0;
For(i, 1, n) {
if (!mp.count(a[i])) vec.pb(i), sum += calc(i, n);
mp[a[i]] = 1;
}
int ans = sum;
set<int> ss;
for (int x : vec) {
auto it = ss.lower_bound(a[x]);
if (it != ss.end()) cmin(ans, sum + (*it) - a[x] - calc(x, las[x] - 1));
if (it != ss.begin()) {
it--;
cmin(ans, sum + a[x] - (*it) - calc(x, las[x] - 1));
}
}
Ace_taffy tr(n);
sort(all(vec), [&](int x, int y) { return a[x] > a[y]; });
for (int x : vec) {
cmin(ans, sum + tr.ask(1, 1, n, x + 1, n) + calc(las[x], n) - a[x]);
tr.add(1, 1, n, x, a[x] - calc(x, n));
}
tr = Ace_taffy(n);
reverse(all(vec));
for (int x : vec) {
cmin(ans, sum + tr.ask(1, 1, n, x + 1, n) + calc(las[x], n) + a[x]);
tr.add(1, 1, n, x, -a[x] - calc(x, n));
}
cout << ans << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
1 4 1 2 3 4
output:
22
result:
ok "22"
Test #2:
score: 0
Accepted
time: 150ms
memory: 3764kb
input:
100000 10 873324878 873324878 873324878 873324878 891656676 891656676 615245360 873324878 873324878 873324878 10 560723194 560723194 797429144 797429144 560723194 797429144 819647695 560723194 797429144 560723194 10 750627649 746781323 756277046 756277046 750627649 750627649 756277046 750627649 9142...
output:
134 141 180 168 109 95 181 185 144 149 202 158 161 107 210 210 255 104 210 109 82 158 149 201 154 109 206 158 161 161 158 134 206 198 161 109 143 152 183 156 171 201 149 104 210 161 181 152 152 250 185 243 206 158 152 128 147 203 225 143 203 198 206 201 158 109 114 100 183 161 162 183 154 222 181 14...
result:
ok 100000 tokens
Test #3:
score: 0
Accepted
time: 202ms
memory: 3864kb
input:
39978 23 512481863 596944631 624383245 441725511 441725511 594496544 441725511 624383245 698754670 596944631 182448912 636350614 596944631 391310300 624383245 391310300 698754670 596944631 441725511 182448912 826649520 351713941 596944631 24 789886131 679943285 874352131 191233114 214841280 21484128...
output:
2322 2416 4226 1974 3362 1631 2373 2521 3618 4540 2589 2104 2692 1407 2757 2394 3938 2106 2769 3209 3418 3828 2339 3954 5404 3191 1734 4260 2178 1354 2829 2552 2820 2385 3102 3442 3459 3027 3631 2399 1682 4564 4494 4217 3756 4176 3290 4109 1702 3740 4220 4117 2118 1840 4223 3499 3834 2472 5465 1636 ...
result:
ok 39978 tokens
Test #4:
score: -100
Wrong Answer
time: 233ms
memory: 3628kb
input:
10000 100 70652501 126219335 870011044 503878453 331807482 42366188 570696778 892481058 11179909 898060545 596710776 892481058 892481058 126219335 938507063 540380652 869222706 898060545 380041360 643567581 977928808 655190742 75768776 126219335 386687451 513015608 898060545 540380652 798597796 7794...
output:
156439 177539 142728 105896 98255 145550 158303 139241 142500 123767 164463 173494 162837 133032 161874 108825 159157 176582 143686 146818 161864 166700 93293 121994 166017 96652 176532 106752 141748 145107 147984 139577 153293 146263 112899 130505 178781 186526 162804 138862 106517 170352 136899 13...
result:
wrong answer 723rd words differ - expected: '172740', found: '173026'