Submission #1248496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248496		phuonglinhn09	Pilot (NOI19_pilot)	C++20	100 / 100	453 ms	113268 KiB

pilot

/**
 *   author:   phuonglinhn09
 *   created:  25.07.2025
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int nmax = 1e6;

int n, q, Arr[nmax + 5];
vector<int> a[nmax + 5], query[nmax + 5];

namespace DSU{
    int par[nmax + 5], sz[nmax + 5];

    void preprocess() {
        for (int i = 1; i <= n; i++) {
            par[i] = i, sz[i] = 1;
        }
    }

    int find_set(int u) {
        return u == par[u] ? u : par[u] = find_set(par[u]);
    }

    ll getVal(int cnt) {
        return 1ll * cnt * (cnt + 1) / 2;
    }

    ll Union(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return 0;

        ll ans = getVal(sz[u] + sz[v]) - getVal(sz[u]) - getVal(sz[v]);
        par[v] = u, sz[u] += sz[v];
        return ans;
    }
}

namespace SOLVE{
    ll ans[nmax + 5];

    void solve(){
        DSU::preprocess();

        ll curAns = 0;
        for (int i = 1; i <= nmax; i++) {
            for (auto pos:a[i]) {
                curAns++;
                //cout << i << " " << pos << ": ";
                if (pos > 1 && Arr[pos - 1] != 0) curAns += DSU::Union(pos - 1, pos);
                //cout << curAns << " ";
                if (pos < n && Arr[pos + 1] != 0) curAns += DSU::Union(pos + 1, pos);
                //cout << curAns << "\n";
                Arr[pos] = i;
            }
            for (auto x:query[i]) ans[x] = curAns;
        }

        for (int i = 1; i <= q; i++) {
            cout << ans[i] << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen (".INP", "r")) {
        freopen (".INP", "r", stdin);
        freopen (".OUT", "w", stdout);
    }

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        a[x].emplace_back(i);
    }
    for (int i = 1; i <= q; i++) {
        int x; cin >> x;
        query[x].emplace_back(i);
    }

    SOLVE::solve();

    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:76:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen (".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
pilot.cpp:77:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen (".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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