제출 #1188502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188502		tahiringotunusiken	Pilot (NOI19_pilot)	C++20	100 / 100	392 ms	39828 KiB

pilot

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

const int MAXN = 1000005;
int parent_[MAXN];
int sz[MAXN];
bool active[MAXN];

int find_set(int v) {
    if (parent_[v] == v) return v;
    return parent_[v] = find_set(parent_[v]);
}

// Global answer of total flights
ll answer = 0;

void unite(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    // remove old contributions
    ll sa = sz[a];
    ll sb = sz[b];
    answer -= sa * (sa + 1) / 2;
    answer -= sb * (sb + 1) / 2;
    // union by size
    if (sz[a] < sz[b]) swap(a, b);
    parent_[b] = a;
    sz[a] += sz[b];
    ll sc = sz[a];
    // add new contribution
    answer += sc * (sc + 1) / 2;
}

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

    int N, Q;
    cin >> N >> Q;
    vector<pair<int,int>> H(N);
    for (int i = 0; i < N; i++) {
        cin >> H[i].first;
        H[i].second = i;
    }
    vector<pair<int,int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].first;
        queries[i].second = i;
    }
    // sort mountains by height
    sort(H.begin(), H.end());
    // sort queries by Y
    sort(queries.begin(), queries.end());
    
    vector<ll> result(Q);
    
    // initialize DSU arrays
    for (int i = 0; i < N; i++) {
        parent_[i] = i;
        sz[i] = 0;
        active[i] = false;
    }
    answer = 0;
    
    int idx = 0;
    for (auto &q : queries) {
        int Y = q.first;
        int qi = q.second;
        // activate all mountains with height <= Y
        while (idx < N && H[idx].first <= Y) {
            int pos = H[idx].second;
            active[pos] = true;
            parent_[pos] = pos;
            sz[pos] = 1;
            // new segment contribution
            answer += 1; // 1 * (1 + 1) / 2 = 1
            // merge with neighbors if active
            if (pos > 0 && active[pos - 1]) unite(pos, pos - 1);
            if (pos + 1 < N && active[pos + 1]) unite(pos, pos + 1);
            idx++;
        }
        result[qi] = answer;
    }
    
    // output in original order
    for (int i = 0; i < Q; i++) {
        cout << result[i] << '\n';
    }
    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