Submission #1096486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096486		Trisanu_Das	Pilot (NOI19_pilot)	C++17	89 / 100	1014 ms	102804 KiB

pilot

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second

int pairs(int l, int r){
    int len = r - l + 1;
    return len * (len + 1) / 2;
}

signed main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL);
    int n, q; cin >> n >> q;
    vector<pair<int, int> > qries(q), h(n);
    int ans[q];
    for(int i = 0; i < n; i++) {
        cin >> h[i].ff; h[i].ss = i;
    } 
    for(int i = 0; i < q; i++){
        cin >> qries[i].ff; qries[i].ss = i;
    }
    sort(qries.rbegin(), qries.rend());
    sort(h.begin(), h.end());
    set<int> s({-1, n});
    int curr = n - 1, ans_curr = n * (n + 1) / 2;
    for(auto qry : qries){
        int val = qry.ff, idx = qry.ss;
        while(curr > -1 && h[curr].ff > val){
            auto it = s.lower_bound(h[curr].ss);
            int r = *it, l = *(--it);
            r--; l++;
            ans_curr += pairs(l, h[curr].ss - 1) +
                   pairs(h[curr].ss + 1, r) -
                   pairs(l, r);
            s.insert(h[curr].ss); curr--;
        }
        ans[idx] = ans_curr;
    }
    for(auto a : ans) cout << a << '\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