Submission #1086770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086770		Muhammad_Aneeq	Pilot (NOI19_pilot)	C++17	89 / 100	1046 ms	122036 KiB

pilot

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const N=1e6+10,LG=22;
int fen[N]={};
int sp[N][LG];
int h[N];
int n,q;
void build()
{
    for (int i=0;i<n;i++)
        sp[i][0]=h[i];
    for (int i=1;(1<<i)<=n;i++)
        for (int j=0;j+(1<<i)-1<n;j++)
            sp[j][i]=max(sp[j][i-1],sp[j+(1<<(i-1))][i-1]);
}
int get(int l,int r)
{
    int lg=log2(r-l+1);
    return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
inline void solve()
{
    cin>>n>>q;
    for (int i=0;i<n;i++)
        cin>>h[i];
    build();
    vector<pair<int,int>>d;
    for (int i=0;i<n;i++)
        d.push_back({h[i],i});
    sort(begin(d),end(d));
    long long ANS[q]={};
    vector<pair<int,int>>Q;
    for (int i=0;i<q;i++)
    {
        int x;
        cin>>x;
        Q.push_back({x,i});
    }
    sort(begin(Q),end(Q));
    int i=0;
    long long pre=0;
    for (auto k:Q)
    {
        int ind,mx;
        tie(mx,ind)=k;
        vector<int>g;
        long long ans=pre;
        while (i<n&&d[i].first<=mx)
        {
            g.push_back(d[i].second);
            i++;
        }
        sort(begin(g),end(g));
        int p=-1;
        for (auto j:g)
        {
            int st=p,en=j;
            while (st+1<en)
            {
                int mid=(st+en)/2;
                if (get(mid,j)<=mx)
                    en=mid;
                else
                    st=mid;
            }
            long long l1=j-en+1;
            st=j,en=n;
            while (st+1<en)
            {
                int mid=(st+en)/2;
                if (get(j,mid)<=mx)
                    st=mid;
                else
                    en=mid;
            }
            long long l2=st-j+1;
            ans+=(l1-1)*(l2-1);
            ans+=(l1-1);
            ans+=(l2-1);
            ans++;
            p=j;
        }
        ANS[ind]=ans;
        pre=ans;
    }
    for (auto i:ANS)
        cout<<i<<'\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: 0 / 11