Submission #970282

#	Time	Username	Problem	Language	Result	Execution time	Memory
970282		VMaksimoski008	Pilot (NOI19_pilot)	C++17	100 / 100	572 ms	75308 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int maxn = 1e6 + 5;
 
int par[maxn], sz[maxn];
 
void init(int n) {
    for(int i=0; i<n; i++) par[i] = i, sz[i] = 1;
}
 
int get(int x) {
    if(x == par[x]) return x;
    return par[x] = get(par[x]);
}
 
bool uni(int a, int b) {
    a = get(a);
    b = get(b);
 
    if(a == b) return 1;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
 
    return 1;
}
 
bool sameSet(int u, int v) { return get(u) == get(v); }
int getSize(int u) { return sz[get(u)]; }
 
struct Query {
    int t, a, b, w;
    bool operator<(Query &e) {
        if(w == e.w) return (t < e.t);
        return w < e.w;
    }
};
 
ll C(ll x) {
    return x * (x - 1) / 2;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    
    int n, q;
    cin >> n >> q;
 
    vector<int> v(n);
    vector<Query> qus;
 
    for(int &x : v) cin >> x;
 
    for(int i=1; i<n; i++)
        qus.push_back({ 2, i-1, i, max(v[i], v[i-1]) });
    for(int i=0; i<n; i++)
        qus.push_back({ 1, i, i, v[i] });
    
    for(int i=0; i<q; i++) {
        int x;
        cin >> x;
        qus.push_back({ 3, i, i, x });
    }
 
    sort(qus.begin(), qus.end());
    vector<ll> ans(q);
    ll res = 0;
    init(n);
 
    for(Query &qu : qus) {
        if(qu.t == 1) {
            res++;
        } else if(qu.t == 2) {
            res -= ( C(getSize(qu.a)) + C(getSize(qu.b)) );
            uni(qu.a, qu.b);
            res += C(getSize(qu.a));
        } else {
            ans[qu.a] = res;
        }
    }
 
    for(ll &x : ans) cout << x << '\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