Submission #860297

#	Time	Username	Problem	Language	Result	Execution time	Memory
860297		annabeth9680	Pilot (NOI19_pilot)	C++17	100 / 100	445 ms	86552 KiB

pilot

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