제출 #1126638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126638		underwaterkillerwhale	Pilot (NOI19_pilot)	C++20	100 / 100	673 ms	50600 KiB

pilot

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

int n, Q;
pii a[N];
pii qr[N];

struct Disjoin_Set {
    ll res = 0;
    int dd[N], lab[N], sz[N];

    void make (int pos) {
        dd[pos] = 1;
        lab[pos] = pos;
        sz[pos] = 1;
        res++;
    }

    int Find (int u) {
        return u == lab[u] ? u : lab[u] = Find(lab[u]);
    }

    void Join (int u, int v) {
        if (!dd[u] || !dd[v]) return;
        u = Find(u);
        v = Find(v);
        if (u == v) return;
        if (sz[u] < sz[v]) swap(u, v);
        res -= 1LL * sz[u] * (sz[u] + 1) / 2;
        res -= 1LL * sz[v] * (sz[v] + 1) / 2;
        sz[u] += sz[v];
        res += 1LL * sz[u] * (sz[u] + 1) / 2;
        lab[v] = u;
    }
}DSU;

void solution() {
    cin >> n >> Q;
    vector<int> vals;
    rep (i, 1, n) {
        cin >> a[i].fs;
        a[i].se = i;
        vals.pb(a[i].fs);
    }
    rep (i, 1, Q) {
        cin >> qr[i].fs;
        qr[i].se = i;
        vals.pb(qr[i].fs);
    }
    sort (a + 1, a + 1 + n);
    sort (qr + 1, qr + 1 + Q);
    sort (ALL(vals));
    vals.resize(unique(ALL(vals)) - vals.begin());
    vector<ll> Ans(Q + 3, 0);
    int ptr = 1, ptrQ = 1;
    iter (&X, vals) {
        while (ptr <= n && a[ptr].fs <= X) {
            int pos = a[ptr].se;
            DSU.make(pos);
            DSU.Join(pos, pos + 1);
            DSU.Join(pos, pos - 1);
            ++ptr;
        }
        while (ptrQ <= Q && qr[ptrQ].fs == X) {
            Ans[qr[ptrQ].se] = DSU.res;
            ++ptrQ;

        }
    }
    rep (i, 1, Q) cout << Ans[i] <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +34
2 1
0 1
*/

• 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