제출 #1126636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126636		underwaterkillerwhale	Pilot (NOI19_pilot)	C++20	89 / 100	1004 ms	96852 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;
int a[N];
vector<pii> vec[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];
        vec[a[i]].pb({1, i});
        vals.pb(a[i]);
    }
    rep (i, 1, Q) {
        int X;
        cin >> X;
        vec[X].pb({0, i});
        vals.pb(X);
    }
    sort (ALL(vals));
    vals.resize(unique(ALL(vals)) - vals.begin());
    vector<ll> Ans(Q + 3, 0);
    iter (&X, vals) {
        iter (&id, vec[X]) {
            if (id.fs == 1) {
                DSU.make(id.se);
                DSU.Join(id.se, id.se + 1);
                DSU.Join(id.se, id.se - 1);
            }
            else {
                Ans[id.se] = DSU.res;
            }
        }
    }
    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 +33
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: 0 / 11