Submission #1086782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086782		Muhammad_Aneeq	Pilot (NOI19_pilot)	C++17	100 / 100	345 ms	52536 KiB

pilot

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const N=1e6+10;
int h[N];
int n,q;
long long ANS[N]={};
int pa[N]={};
long long sz[N]={};
int root(int n)
{
    int z=n;
    while (pa[z]!=z)
        z=pa[z];
    int g=z;
    z=n;
    while (pa[z]!=z)
    {
        int f=pa[z];
        pa[z]=g;
        z=f;
    }
    return pa[n];
}
long long ans=0;
void merge(int u,int v)
{
    u=root(u);
    v=root(v);
    if (u==v)
        return;
    ans+=(sz[u]*sz[v]);
    sz[u]+=sz[v];
    pa[v]=u;
}
inline void solve()
{
    cin>>n>>q;
    for (int i=0;i<n;i++)
        cin>>h[i];
    for (int i=0;i<N;i++)
        pa[i]=i,sz[i]=1;
    vector<pair<int,int>>d;
    for (int i=0;i<n;i++)
        d.push_back({h[i],i});
    sort(begin(d),end(d));
    int i=0;
    for (int mx=1;mx<N;mx++)
    {
        while (i<n&&d[i].first==mx)
        {
            if (d[i].second>0&&h[d[i].second-1]<=mx)
                merge(d[i].second,d[i].second-1);
            if (d[i].second+1<n&&h[d[i].second+1]<=mx)
                merge(d[i].second,d[i].second+1);
            i++;
            ans++;
        }
        ANS[mx]=ans;
    }
    while (q--)
    {
        int x;
        cin>>x;
        cout<<ANS[x]<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

• 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