Submission #970269

#	Time	Username	Problem	Language	Result	Execution time	Memory
970269		VMaksimoski008	Pilot (NOI19_pilot)	C++17	89 / 100	1022 ms	136192 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;
 
struct DSU {
    int n, comp;
    vector<int> par, size;
 
    void config(int _n) {
        n = _n + 1;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }
 
    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }
 
    bool uni(int u, int v) {
        u = get(u), v = get(v);
 
        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);
 
        size[u] += size[v];
        par[v] = u;
 
        return true;
    }
 
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
};
 
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;
}

vector<int> mp[maxn+1];
 
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({ 1, i-1, i, max(v[i], v[i-1]) });
    
    for(int i=0; i<q; i++) {
        int x;
        cin >> x;
        mn = min(mn, x);
        qus.push_back({ 2, i, i, x });
    }
 
    sort(qus.begin(), qus.end());
    vector<ll> ans(q);
    ll res = 0;
 
    for(int i=0; i<n; i++) mp[v[i]].push_back(i);
 
    set<int> s;
    for(int &x : v) s.insert(x);
    vector<int> comp(s.begin(), s.end());
 
    int ptr = 0;
    DSU dsu; dsu.config(n);
 
    for(Query &qu : qus) {
        while(ptr < comp.size() && comp[ptr] <= qu.w) {
            for(int &p : mp[comp[ptr]]) res++;
            ptr++;
        }
 
        if(qu.t == 1) {
            if(dsu.sameSet(qu.a, qu.b)) continue;
            res -= C(dsu.getSize(qu.a));
            res -= C(dsu.getSize(qu.b));
            dsu.uni(qu.a, qu.b);
            res += C(dsu.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:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         while(ptr < comp.size() && comp[ptr] <= qu.w) {
      |               ~~~~^~~~~~~~~~~~~
pilot.cpp:95:22: warning: unused variable 'p' [-Wunused-variable]
   95 |             for(int &p : mp[comp[ptr]]) res++;
      |                      ^

• 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: 0 / 11