Submission #797927

#	Time	Username	Problem	Language	Result	Execution time	Memory
797927		vjudge1	Construction of Highway (JOI18_construction)	C++17	16 / 100	275 ms	612 KiB

construction

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5000;

int n;
int p[N];
int C[N];

ll numberOfInverse(int *a, int n) {
    static int b[N];
    if(n == 1) return 0;
    ll ans = numberOfInverse(a, n / 2) + numberOfInverse(a + n / 2, (n + 1) / 2);
    int lb = 0, rb = 0;
    for(int i = n / 2; i < n; i++) {
        while(lb < n / 2 && a[lb] <= a[i]) lb++;
        ans += n / 2 - lb;
    }
    lb = 0, rb = n / 2;
    for(int i = 0; i < n; i++) {
        if(lb == n / 2) {
            b[i] = a[rb++];
            continue;
        }
        if(rb == n) {
            b[i] = a[lb++];
            continue;
        }
        b[i] = (a[lb] <= a[rb] ? a[lb++] : a[rb++]);
    }
    for(int i = 0; i < n; i++) 
        a[i] = b[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> C[i];
    for(int i = 1; i <= n - 1; i++) {
        int A, B;
        cin >> A >> B;
        int vals[n], len = 0;
        int cur = A;
        while(cur) {
            vals[len++] = C[cur];
            cur = p[cur];
        }
        reverse(vals, vals + len);
        cout << numberOfInverse(vals, len) << '\n';
        
        p[B] = A;
        cur = A;
        while(cur) {
            C[cur] = C[B];
            cur = p[cur];
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84