Submission #970281

#	Time	Username	Problem	Language	Result	Execution time	Memory
970281		VMaksimoski008	Pilot (NOI19_pilot)	C++17	100 / 100	628 ms	88604 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
 
using ll = long long;
using pii = pair<int, int>;
 
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;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    
    int n, q, mn = 1e9;
    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;
        mn = min(mn, x);
        qus.push_back({ 3, i, i, x });
    }
 
    sort(qus.begin(), qus.end());
    vector<ll> ans(q);
    ll res = 0;
 
    int ptr = 0;
    init(n);
 
    for(Query &qu : qus) {
        if(qu.t == 1) {
            res++;
        } else if(qu.t == 2) {
            if(sameSet(qu.a, qu.b)) continue;
            res -= C(getSize(qu.a));
            res -= 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;
}

Compilation message (stderr)

pilot.cpp: In function 'int32_t main()':
pilot.cpp:78:9: warning: unused variable 'ptr' [-Wunused-variable]
   78 |     int ptr = 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