87022024-01-25 20:23:58szilFurcsa műveletcpp17Accepted 100/100828ms288824 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;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1844 KiB
2Accepted3ms2180 KiB
subtask214/14
3Accepted78ms9812 KiB
4Accepted74ms9808 KiB
5Accepted71ms10052 KiB
6Accepted82ms10156 KiB
7Accepted82ms10488 KiB
8Accepted85ms10464 KiB
9Accepted3ms3132 KiB
10Accepted3ms3244 KiB
11Accepted3ms3352 KiB
12Accepted3ms3208 KiB
13Accepted2ms3264 KiB
subtask318/18
14Accepted3ms3524 KiB
15Accepted3ms3384 KiB
16Accepted2ms3532 KiB
17Accepted2ms3388 KiB
18Accepted2ms3388 KiB
19Accepted3ms3704 KiB
20Accepted2ms3716 KiB
subtask450/50
21Accepted4ms5196 KiB
22Accepted4ms5196 KiB
23Accepted4ms5212 KiB
24Accepted4ms5304 KiB
25Accepted4ms5392 KiB
26Accepted3ms3896 KiB
27Accepted3ms3788 KiB
subtask518/18
28Accepted683ms288488 KiB
29Accepted736ms288248 KiB
30Accepted785ms288444 KiB
31Accepted828ms288716 KiB
32Accepted671ms288824 KiB
33Accepted648ms288736 KiB
34Accepted57ms7380 KiB
35Accepted57ms7444 KiB