Submission #970272

#	Time	Username	Problem	Language	Result	Execution time	Memory
970272		VMaksimoski008	Pilot (NOI19_pilot)	C++17	89 / 100	1088 ms	123056 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;
}

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;
    init(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(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:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while(ptr < comp.size() && comp[ptr] <= qu.w) {
      |               ~~~~^~~~~~~~~~~~~
pilot.cpp:89:22: warning: unused variable 'p' [-Wunused-variable]
   89 |             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