Submission #743696

#	Time	Username	Problem	Language	Result	Execution time	Memory
743696		KG07	Pilot (NOI19_pilot)	C++14	89 / 100	1034 ms	43564 KiB

pilot

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[2100000];
int h[1000001];
long long d[1000001];
priority_queue<pair<int, int>> q;
void L(int x, int y, bool z){
    int x_ = x, y_ = y;
    if(!z){
        x_ = 0;
        y_ = 0;
    }
    while(x < y){
        if(x % 2 == 1){
            a[x].first = x_;
            a[x].second = y_;
            x++;
        }
        if(y % 2 == 0){
            a[y].first = x_;
            a[y].second = y_;
            y--;
        }
        x /= 2;
        y /= 2;
    }
    if(x == y){
        a[x].first = x_;
        a[y].second = y_;
    }
}
int g(int x){
    while(!a[x].first){
        x /= 2;
    }
    return x;
}

int main() {
    // Write C++ code here
    int n, m;
    cin >> n >> m;
    int k = 1, o = 0;
    while(k < n){
        k *= 2;
    }
    for(int i = 0; i < n; i++){
        cin >> h[i];
        q.push({h[i], i});
        o = max(o, h[i]);
    }
    L(k, k+n-1, true);
    while(!q.empty()){
        int w = q.top().first;
        int z = q.top().second;
        q.pop();
        int t = g(k+z);
        int x = a[t].first, y = a[t].second;
        L(a[t].first, a[t].second, false);
        d[w] += 1ll * (k+z-x+1) * (y-k-z+1);
        if(k+z == x && k+z == y){
            continue;
        }
        if(k+z > x){
            L(x, k+z-1, true);
        }
        if(k+z < y){
            L(k+z+1, y, true);
        }
    }
    for(int i = o; i; i--){
        d[i-1] += d[i];
    }
    for(int i = 0; i < m; i++){
        int w;
        cin >> w;
        cout << 1ll * n * (n+1) / 2 - d[w+1] << "\n";
    }

    return 0;
}

• 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