Submission #969916

#	Time	Username	Problem	Language	Result	Execution time	Memory
969916		VMaksimoski008	Pilot (NOI19_pilot)	C++17	89 / 100	1020 ms	127384 KiB

pilot

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e6 + 5;
const double eps = 1e-9;

struct DSU {
    int n, comp;
    vector<int> par, size;

    void config(int _n) {
        n = _n + 1;
        comp = _n;
        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;
        comp--;

        return true;
    }

    int getComp() { return comp; }
    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;
}

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(all(qus));
    vector<ll> ans(q);
    ll res = 0;

    vector<int> mp[maxn+1];
    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(all(s));

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