8702 | 2024-01-25 20:23:58 | szil | Furcsa művelet | cpp17 | Accepted 100/100 | 828ms | 288824 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200'001;
int a[MAXN], b[MAXN], tree[2*MAXN], n;
void upd(int u) {
tree[u += n]++;
for (u /= 2; u >= 1; u /= 2) {
tree[u] = tree[2*u] + tree[2*u+1];
}
}
int qry(int l, int r) {
l += n; r += n;
int ans = 0;
while (l <= r) {
if (l % 2 == 1) ans += tree[l++];
if (r % 2 == 0) ans += tree[r--];
l /= 2; r /= 2;
}
return ans;
}
int main(){
cin.tie(0); cin.sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
if (a[1] != b[1] || a[n] != b[n]) {
cout << "-1\n";
} else {
map<int, queue<int>> x;
for (int i = 2; i <= n; i++) {
int s = b[i-1] + b[i];
if (i & 1) s *= -1;
x[s].push(i);
}
ll ans = 0;
for (int i = 2; i <= n; i++) {
int s = a[i-1] + a[i];
if (i & 1) s *= -1;
if (x[s].empty()) {
cout << "-1\n";
return 0;
}
upd(x[s].front());
ans += qry(x[s].front()+1, n);
x[s].pop();
}
cout << ans << "\n";
}
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1844 KiB | ||||
2 | Accepted | 3ms | 2180 KiB | ||||
subtask2 | 14/14 | ||||||
3 | Accepted | 78ms | 9812 KiB | ||||
4 | Accepted | 74ms | 9808 KiB | ||||
5 | Accepted | 71ms | 10052 KiB | ||||
6 | Accepted | 82ms | 10156 KiB | ||||
7 | Accepted | 82ms | 10488 KiB | ||||
8 | Accepted | 85ms | 10464 KiB | ||||
9 | Accepted | 3ms | 3132 KiB | ||||
10 | Accepted | 3ms | 3244 KiB | ||||
11 | Accepted | 3ms | 3352 KiB | ||||
12 | Accepted | 3ms | 3208 KiB | ||||
13 | Accepted | 2ms | 3264 KiB | ||||
subtask3 | 18/18 | ||||||
14 | Accepted | 3ms | 3524 KiB | ||||
15 | Accepted | 3ms | 3384 KiB | ||||
16 | Accepted | 2ms | 3532 KiB | ||||
17 | Accepted | 2ms | 3388 KiB | ||||
18 | Accepted | 2ms | 3388 KiB | ||||
19 | Accepted | 3ms | 3704 KiB | ||||
20 | Accepted | 2ms | 3716 KiB | ||||
subtask4 | 50/50 | ||||||
21 | Accepted | 4ms | 5196 KiB | ||||
22 | Accepted | 4ms | 5196 KiB | ||||
23 | Accepted | 4ms | 5212 KiB | ||||
24 | Accepted | 4ms | 5304 KiB | ||||
25 | Accepted | 4ms | 5392 KiB | ||||
26 | Accepted | 3ms | 3896 KiB | ||||
27 | Accepted | 3ms | 3788 KiB | ||||
subtask5 | 18/18 | ||||||
28 | Accepted | 683ms | 288488 KiB | ||||
29 | Accepted | 736ms | 288248 KiB | ||||
30 | Accepted | 785ms | 288444 KiB | ||||
31 | Accepted | 828ms | 288716 KiB | ||||
32 | Accepted | 671ms | 288824 KiB | ||||
33 | Accepted | 648ms | 288736 KiB | ||||
34 | Accepted | 57ms | 7380 KiB | ||||
35 | Accepted | 57ms | 7444 KiB |