Submission #484081

#	Time	Username	Problem	Language	Result	Execution time	Memory
484081		CyberSleeper	Pilot (NOI19_pilot)	C++14	100 / 100	522 ms	69956 KiB

pilot

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define pll         pair<ll, ll>
#define ull         unsigned long long
#define ld          long double
#define pii         pair<ll, ll>
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=1000007, MOD=1e9+7, BLOCK=330, INF=1e9+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

ll N, Q, H[MX], ptr=0;
ll tot=0, ans[MX];
pii A[MX], Y[MX];

ll calc(ll x){
    return x*(1ll+x)/2ll;
}
struct dsu{
    ll par[MX], sz[MX];
    dsu(){
        for(ll i=0; i<MX; i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    ll f(ll u){
        if(par[u]!=u)
            par[u]=f(par[u]);
        return par[u];
    }
    void join(ll u, ll v){
        u=f(u);
        v=f(v);
        if(u==v)
            return;
        if(sz[u]>sz[v])
            swap(u, v);
        tot-=calc(sz[u])+calc(sz[v]);
        par[u]=v;
        sz[v]+=sz[u];
        tot+=calc(sz[v]);
    }
}DSU;

int main(){
    fastio;
    cin >> N >> Q;
    for(ll i=0; i<N; i++){
        cin >> H[i];
        A[i]={H[i], i};
    }
    for(ll i=0; i<Q; i++){
        cin >> Y[i].fi;
        Y[i].se=i;
    }
    sort(Y, Y+Q);
    sort(A, A+N);
    for(ll i=0; ptr<Q && i<N; i++){
        ll h=A[i].fi, idx=A[i].se;
        while(ptr<Q && Y[ptr].fi<h)
            ans[Y[ptr++].se]=tot;
        if(ptr>=Q)
            break;
        tot++;
        if(idx && H[idx-1]<=h)
            DSU.join(idx-1, idx);
        if(idx+1<N && H[idx+1]<=h)
            DSU.join(idx+1, idx);
    }
    while(ptr<Q)
        ans[Y[ptr++].se]=tot;
    for(ll i=0; i<Q; i++){
        cout << ans[i] << nl;
    }
}

• 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