Submission #1086765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086765		Muhammad_Aneeq	Pilot (NOI19_pilot)	C++17	89 / 100	1035 ms	47908 KiB

pilot

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int const N=1e6+10;
int St[4*N]={};
int h[N];
int n,q;
int get(int l,int r,int i=1,int st=0,int en=N)
{
    if (st>=l&&en<=r)
        return St[i];
    if (st>r||en<l)
        return 0;
    int mid=(st+en)/2;
    return get(l,r,i*2,st,mid)+get(l,r,i*2+1,mid+1,en);
}
void update(int r,int i=1,int st=0,int en=N)
{
    if (st==en)
    {
        St[i]=1;
        return;
    }
    int mid=(st+en)/2;
    if (r<=mid)
        update(r,i*2,st,mid);
    else
        update(r,i*2+1,mid+1,en);
    St[i]=St[i*2]+St[i*2+1];
}
inline void solve()
{
    cin>>n>>q;
    for (int i=0;i<n;i++)
        cin>>h[i];
    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 mx=k.first;
        vector<int>g;
        long long ans=pre;
        while (i<n&&d[i].first<=mx)
        {
            g.push_back(d[i].second);
            i++;
        }
        for (auto j:g)
        {
            update(j);
            int st=-1,en=j;
            while (st+1<en)
            {
                int mid=(st+en)/2;
                if (get(mid,j)==j-mid+1)
                    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)==mid-j+1)
                    st=mid;
                else
                    en=mid;
            }
            long long l2=st-j+1;
            ans+=(l1-1)*(l2-1);
            ans+=l2+l1-2;
            ans++;
        }
        ANS[k.second]=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