Submission #1140831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140831		altern23	Pilot (NOI19_pilot)	C++20	100 / 100	472 ms	106748 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

const ll MOD = 998244353;
const ll N = 1e6;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

ll tot, n, q;
ll h[N + 5];

struct DSU{
    ll n;
    vector<ll> par, sz, val;
    DSU(ll _n){
        n = _n;
        par.resize(n + 5);
        sz.resize(n + 5);
        val.resize(n + 5);
        for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    }
    
    ll find(ll idx){
        if(par[idx] == idx) return idx;
        return par[idx] = find(par[idx]);
    }

    void join(ll a, ll b){
        a = find(a), b = find(b);
        if(a == b) return;
        tot -= sz[a] * (sz[a] + 1) / 2;
        tot -= sz[b] * (sz[b] + 1) / 2;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b], sz[b] = 0;
        par[b] = a;
        tot += sz[a] * (sz[a] + 1) / 2;
    }

    void F(ll idx, ll &_n){
        // diri sendiri
        sz[idx] = 1;
        tot++;
        // bisa join kiri
        if(idx - 1 >= 1 && h[idx] >= h[idx - 1]){
            join(idx - 1, idx);
        }
        // bisa join kanan
        if(idx + 1 <= _n && h[idx] >= h[idx + 1]){
            join(idx, idx + 1);
        }
    }
} dsu(N);

vector<ll> pos[N + 5];

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        cin >> n >> q;
        for(int i = 1; i <= n; i++){
            cin >> h[i];
            pos[h[i]].push_back(i);
        }

        vector<pii> Q(q + 5);
        vector<ll> ans(q + 5);
        for(int i = 1; i <= q; i++){
            cin >> Q[i].fi;
            Q[i].sec = i;
        }

        sort(Q.begin() + 1, Q.begin() + 1 + q);

        ll cur = 1;
        for(int i = 1; i <= q; i++){
            for(;cur <= Q[i].fi;){
                for(auto &x : pos[cur]){
                    dsu.F(x, n);
                }
                cur++;
            }
            ans[Q[i].sec] = tot;
            // cout << tot << "\n";
        }

        for(int i = 1; i <= q; i++) cout << ans[i] << "\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