제출 #1173523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173523		qrn	Pilot (NOI19_pilot)	C++20	26 / 100	34 ms	14396 KiB

pilot

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 1e6 + 5;
const intt L = 21;

vector<intt> processed(mxN);
intt ans = 0;
struct DSU{
    vector<intt> parent, sze;
    DSU(intt n) {
        parent.resize(n + 1);
        sze.resize(n + 1);
        for(intt i = 0; i <= n; i++){
            parent[i] = i;
            sze[i] = 1;
        }
    }
    
    intt root(intt x) {
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }
    
    void unite(intt a, intt b) {  
        intt ka = a, kb = b;
        a = root(a);
        b = root(b);
        if(a == b) return;
        // cout << ka << " " << kb << ": " << sze[a] << " " << sze[b] << " :: " << ans << endl;
        ans -= (sze[a] * (sze[a] + 1)) / 2;
        ans -= (sze[b] * (sze[b] + 1)) / 2;
        if(sze[a] < sze[b]) swap(a, b);
        parent[b] = a;
        sze[a] += sze[b];
        ans += (sze[a] * (sze[a] + 1)) / 2;
    }
};

void solve() {
    intt n, q;
    cin >> n >> q;
    vector<pair<intt,intt>> a, qrys;
    processed.resize(n + 1);
    for(intt i = 0; i < n; i++) {
        intt x;
        cin >> x;
        a.pb({x,i});
    }    
    
    vector<intt> cvb(q);
    for(intt i = 0; i < q; i++) {
        intt x;
        cin >> x;
        qrys.pb({x,i});
    }
    sort(ALL(a)); sort(ALL(qrys));
    DSU dsu(n + 1);
    intt idx = 0;
    for(intt i = 0; i < q; i++) {
        while(a[idx].fi <= qrys[i].fi && idx < n) {
            ans++;
            if(idx != 0 && processed[a[idx].se-1]) dsu.unite(a[idx].se, a[idx].se-1);
            if(idx != n - 1 && processed[a[idx].se+1]) dsu.unite(a[idx].se, a[idx].se+1);
            processed[a[idx].se] = 1;
            ++idx;
        }
        cvb[qrys[i].se] = ans;
    }
    
    for(intt i = 0; i < q; i++) {
        cout << cvb[i] << endl;
    }
    
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 0 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11