QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246462#7079. ArrayyyzWA 233ms3864kbC++142.5kb2023-11-10 20:40:482023-11-10 20:40:49

Judging History

你现在查看的是最新测评结果

  • [2023-11-10 20:40:49]
  • 评测
  • 测评结果:WA
  • 用时:233ms
  • 内存:3864kb
  • [2023-11-10 20:40:48]
  • 提交

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'