Submission #320742

#	Time	Username	Problem	Language	Result	Execution time	Memory
320742		arujbansal	Pilot (NOI19_pilot)	C++17	100 / 100	738 ms	75552 KiB

pilot

#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int N = 1e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;

struct UFDS {
    int n, validFlights;
    vector<int> par, s;
    vector<bool> active;

    void init(int x) {
        n = x;
        validFlights = 0;
        par.resize(n);
        iota(all(par), 0);
        s.assign(n, 1);
        active.assign(n, false);
    }

    int get(int x) {
        if (par[x] == x) return x;
        return par[x] = get(par[x]);
    }

    bool unite(int x, int y) {
        x = get(x);
        y = get(y);

        if (!active[x]) {
            active[x] = true;
            validFlights += s[x];
        }

        if (!active[y] || x == y) return false;

        if (s[x] < s[y]) swap(x, y);

        validFlights -= flights(s[x]) + flights(s[y]);


        s[x] += s[y];
        par[y] = x;

        validFlights += flights(s[x]);

        return true;
    }

    int getSz(int x) {
        x = get(x);
        return s[x];
    }

    int flights(int x) {
        return x * (x + 1) / 2;
    }
};

signed main() {
    FAST_IO;
#ifdef arujbansal_local
    setIO("input.txt", "output.txt");
#endif

    int n, q;
    cin >> n >> q;

    vii h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }

    sort(all(h));

    vii queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].first;
        queries[i].second = i;
    }

    sort(all(queries));

    UFDS mountains;
    mountains.init(n);

    int ans[q];

    int j = 0;
    for (const auto &[plane, idx] : queries) {
        while (j < n && h[j].first <= plane) {
            int cur = h[j].second;
            int prev = cur - 1;
            int next = cur + 1;

            if (prev >= 0) mountains.unite(cur, prev);
            if (next < n) mountains.unite(cur, next);
            j++;
        }

        ans[idx] = mountains.validFlights;
    }

    for (const auto &x : ans) cout << x << "\n";
}

• 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