제출 #1283677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283677		iamhereforfun	Construction of Highway (JOI18_construction)	C++20	16 / 100	121 ms	744 KiB

construction

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 4e3 + 5;
const int M = 3e6 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18 + 5;
const int P = 31;
const int MOD = 998244353;

struct Fenwick
{
    vector<int> ft;
    int n;
    Fenwick(int len)
    {
        n = len;
        ft.assign(n + 1, 0);
    }
    void update(int pos, int val)
    {
        while(pos <= n)
        {
            ft[pos] += val;
            pos += LSOne(pos);
       }
    }
    int get(int pos)
    {
        int sum = 0;
        while(pos > 0)
        {
            sum += ft[pos];
            pos -= LSOne(pos);
        }
        return sum;
    }
    int get(int l, int r)
    {
        if(l > r) return 0;
        return get(r) - get(l - 1);
    }
};

int n, val[N], par[N];
vector<int> adj[N], com;

void solve()
{
    cin >> n;
    for(int x = 1; x <= n; x++)
    {
        cin >> val[x];
        com.push_back(val[x]);
    }
    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    for(int x = 1; x <= n; x++)
    {
        val[x] = lower_bound(com.begin(), com.end(), val[x]) - com.begin() + 1;
    }
    par[1] = 0;
    for(int x = 0; x < n - 1; x++)
    {
        int a, b, c, ans = 0; cin >> a >> b;
        c = a;
        vector<int> v;
        while(c != 0)
        {
            v.push_back(c);
            c = par[c];
        }
        Fenwick ft(com.size());
        while(!v.empty())
        {
            ans += ft.get(val[v.back()] + 1, com.size());
            ft.update(val[v.back()], 1);
            v.pop_back();
        }
        cout << ans << "\n";
        adj[a].push_back(b);
        par[b] = a;
        while(a != 0)
        {
            val[a] = val[b];
            a = par[a];
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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