Submission #491451

#	Time	Username	Problem	Language	Result	Execution time	Memory
491451		beepbeepsheep	Pilot (NOI19_pilot)	C++17	0 / 100	125 ms	262148 KiB

pilot

#include <bits/stdc++.h>

using namespace std;
#define ll int
#define endl '\n'
typedef pair<ll,ll> ii;
//const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=1e6+5;

ll parent[maxn];
ll ran[maxn];
ll sz[maxn];
stack<ll> cnt[maxn];
ll ans[maxn];
bool vis[maxn];
ll root(ll x){
    if (parent[x]==x) return x;
    return parent[x]=root(parent[x]);
}
void connect(ll a,ll b){
    ll root_a=a,root_b=b;
    if (root_a==root_b) return;
    if (ran[root_a]>ran[root_b]){
        sz[root_a]+=sz[root_b];
        parent[root_b]=root_a;
    } else if (ran[root_b]>ran[root_a]){
        sz[root_b]+=sz[root_a];
        parent[root_a]=root_b;
    } else{
        sz[root_a]+=sz[root_b];
        parent[root_b]=root_a;
        ran[root_a]++;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i=0;i<maxn;i++){
        parent[i]=i;
    }
    fill(sz,sz+maxn,1);
    ll n,q,ele;
    cin>>n>>q;
    for (int i=0;i<n;i++){
        cin>>ele;
        cnt[ele].push(i+1);
    }
    for (int i=1;i<maxn;i++){
        ans[i]=ans[i-1];
        while (!cnt[i].empty()){
            ll a=cnt[i].top();
            cnt[i].pop();
            vis[a]=1;
            ll root_l=root(a-1);
            ll root_r=root(a+1);
            if (vis[a-1] && vis[a+1]){
                ans[i]+=sz[root_l]*sz[root_r]+(sz[root_l]+sz[root_r]+1);
                connect(root_l,a);
                connect(root_r,a);
            } else if (vis[a-1]){
                ans[i]+=sz[root_l]+1;
                connect(a,root_l);
            } else if (vis[a+1]){
                ans[i]+=sz[root_r]+1;
                connect(a,root_r);
            } else{
                ans[i]+=1;
            }
        }
    }
    for (int i=0;i<q;i++){
        cin>>ele;
        cout<<ans[ele]<<endl;
    }
    return 0;
}

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