제출 #1024944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024944		lamagril	Pilot (NOI19_pilot)	C++17	89 / 100	1006 ms	110416 KiB

pilot

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int md=1e9+7;

int32_t main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,q; cin >> n >> q;
    vector<int> he(n+1);
    vector<pair<int,int>> h(n+1),y(q+1);
    vector<int> pri(q+1);
    int ans=n*(n+1)/2;
    for(int i=1 ; i<=n ; i++) cin >> h[i].first,he[i]=h[i].first,h[i].second=i;
    for(int i=1 ; i<=q ; i++) cin >> y[i].first,y[i].second=i;
    sort(h.begin(),h.end());
    sort(he.begin(),he.end());
    sort(y.begin(),y.end());
    reverse(y.begin()+1,y.end());
    set<int> s;
    s.insert(0);
    s.insert(n+1);
    int id=n;
    for(int t=1 ; t<=q ; t++){
        int idx=upper_bound(he.begin(),he.end(),y[t].first)-he.begin();
        //cout << "idx== " << idx << " id== " << id << '\n';
        for(int i=idx ; i<=id ; i++){
            s.insert(h[i].second);
            auto itr=s.lower_bound(h[i].second);
            int now=*itr;
            //cout << "itr== " << now << '\n';
            itr--;
            int l=*itr;
            //cout << "itrl== " << l << '\n';
            itr++;
            itr++;
            auto r=*itr;
            //cout << "itrr== " << r << '\n';
            ans-=(now-l-1)*(r-now-1);
            ans-=r-l-1;
            //cout << "ans== " << ans << '\n';
        }
        id=idx-1;
        pri[y[t].second]=ans;
    }
    for(int i=1 ; i<=q ; i++){
        cout << pri[i] << '\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: 0 / 11