Submission #633406

#	Time	Username	Problem	Language	Result	Execution time	Memory
633406		JJAnawat	Pilot (NOI19_pilot)	C++14	100 / 100	771 ms	84660 KiB

pilot

#include<bits/stdc++.h>

using namespace std;

//maximum = 1e6;
const int mxN=1e6;
int n,q,x;
int p[mxN+5];
vector<int> h[mxN+5];
long long ans[mxN+5],sz[mxN+5];
bool vis[mxN+5];

int fp(int i){
    if(p[i]==i)
        return i;
    return p[i]=fp(p[i]);
}

long long cal(long long szx){
    return szx*(szx+1)/2;
}

long long un(int x,int y,long long sum){
    int u=fp(x),v=fp(y);
    sum-=cal(sz[u])+cal(sz[v]);
    if(sz[u]<sz[v])
        swap(u,v);
    p[v]=u;
    sz[u]+=sz[v];
    sum+=cal(sz[u]);
    return sum;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for(int i=1;i<=mxN;i++){
        p[i]=i;
        sz[i]=1;
    }

    for(int i=1;i<=n;i++){
        cin >> x;
        h[x].push_back(i);
    }

    for(int i=1;i<=mxN;i++){
        ans[i]=ans[i-1];
        for(auto j:h[i]){
            vis[j]=1;
            ans[i]++;
            if(vis[j-1])
                ans[i]=un(j,j-1,ans[i]);
            if(vis[j+1])
                ans[i]=un(j,j+1,ans[i]);
        }
    }

    while(q--){
        cin >> x;
        cout << ans[x] << '\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