제출 #853407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853407		annabeth9680	Pilot (NOI19_pilot)	C++17	100 / 100	457 ms	85680 KiB

pilot

#include <bits/stdc++.h>
#define int long long
using namespace std;
int res = 0;
struct dsu{
    vector<int> D,dep;
    void init(int N){
        D.resize(N+1);
        dep.resize(N+1);
        for(int i = 0; i<=N;++i){
            D[i] = i; dep[i] = 1;
        }
    }
    int finden(int x){
        return D[x] = (D[x] == x ? x : finden(D[x]));
    }
    void unite(int a, int b){
        a = finden(a); b = finden(b);
        if(a == b) return;
        res += dep[a]*dep[b];
        D[a] = b; dep[b] += dep[a];
    }
}DSU;
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,Q; cin >> N >> Q;
    vector<int> height(N),ans(Q);
    for(int i = 0;i<N;++i) cin >> height[i];
    DSU.init(N);
    vector<pair<int,int>> queries, edges;
    for(int i = 0;i<Q;++i){
        int x; cin >> x;
        queries.push_back({x,i});
    }
    for(int i = 0;i<N;++i) edges.push_back({height[i],i});
    sort(queries.begin(),queries.end()); sort(edges.begin(),edges.end());
    int pos = 0;
    for(int i = 0;i<Q;++i){
        while(pos < N && queries[i].first >= edges[pos].first){
            DSU.unite(edges[pos].second,edges[pos].second+1);
            pos++;
        }
        ans[queries[i].second] = res;
    }
    for(int i = 0;i<Q;++i) cout << ans[i] << " ";
    cout << "\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