Submission #1340858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340858		Nipphitch	Pilot (NOI19_pilot)	C++20	100 / 100	911 ms	85084 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e6+5;

int n,q;
ll h[N];
ll sum_now,ans[N];
set <int> pos,tmp;
vector <pair <ll,int>> vec;

ll cal(ll x){
    return x*(x+1)/2;
}

bool cmp(pair <ll,int> x,pair <ll,int> y){
    if(x.first!=y.first) return x.first>y.first;
    else return x.second<y.second;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> h[i];
        vec.push_back({h[i],i});
    }
    sum_now=cal(n);
    ans[N-1]=sum_now;
    pos.insert(0);
    pos.insert(n+1);
    sort(vec.begin(),vec.end(),cmp);
    vec.push_back({0,-1});
    memset(ans,-1,sizeof(ans));
    int pv=-1;
    for(auto [h_i,idx]:vec){
        if(pv!=h_i) ans[h_i]=sum_now;
        if(idx==-1) continue;
        auto itr=pos.lower_bound(idx);
        auto itl=prev(itr);
        int l=*itl,r=*itr;
        sum_now-=cal(r-l);
        sum_now+=cal(idx-l)+cal(r-idx);
        pos.insert(idx);
        pv=h_i;
    }
    for(int i=1;i<N;i++) if(ans[i]==-1 && ans[i-1]!=-1) ans[i]=max(ans[i],ans[i-1]);
    while(q--){
        int x;
        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