Submission #1316179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316179		1ota	Pilot (NOI19_pilot)	C++20	100 / 100	436 ms	69940 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

struct DSU{
    int n, cnt = 0;
    vector<bool> vis;
    vector<int> parent, sz;

    DSU (int n) : n(n) {
        sz.resize(n, 1); vis.resize(n, false);
        parent.resize(n); iota(entire(parent), 0ll);
    }

    int pi (int u){
        return (parent[u] == u) ? u : (parent[u] = pi(parent[u]));
    }

    int two (int N) {
        return (N * (N + 1)) / 2;
    };

    void merge (int u, int v){
        u = pi(u); v = pi(v);
        if (u == v) {
            cnt -= two(sz[u]) * vis[u] - two(sz[u]); vis[u] = true; return; 
        }
        if (sz[u] < sz[v]) swap(u, v);
        int delta = two(sz[u]) * vis[u] + two(sz[v]) * vis[v];
        vis[u] = vis[v] = true; parent[v] = u; sz[u] += sz[v];
        delta -= two(sz[u]); cnt -= delta;
    }
};

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> h(n);
    vector<pii> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].ff, a[i].ss = i, h[i] = a[i].ff;

    vector<pii> qn(q); 
    for (int i = 0; i < q; i++) cin >> qn[i].ff, qn[i].ss = i;
    sort(entire(qn)); sort(entire(a));

    DSU dsu(n);

    auto add = [&](int idx){
        dsu.merge(idx, idx);
        if (0 < idx and dsu.vis[idx-1]) dsu.merge(idx, idx-1);
        if (idx < n-1 and dsu.vis[idx+1]) dsu.merge(idx, idx+1);
    };

    int i = 0;
    vector<int> ans(q, 0);

    for (auto [lim, idx] : qn){
        while (i < n and a[i].ff <= lim) add(a[i].ss), i++;
        ans[idx] = dsu.cnt;
    }

    for (auto num : ans) cout << num << " ";
    cout << endl;
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11