Submission #1086780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086780		Muhammad_Aneeq	Pilot (NOI19_pilot)	C++17	78 / 100	168 ms	19660 KiB

pilot

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const N=1e6+10,LG=22;
int h[N];
int n,q;
long long ANS[N]={};
int pa[N]={};
int sz[N]={};
int root(int n)
{
    if (pa[n]==n)
        return n;
    return (pa[n]=root(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]<<endl;
    }
}
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: 0 / 11
• Subtask 10: 0 / 11