Submission #1134822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134822		Roumak77	Pilot (NOI19_pilot)	C++20	78 / 100	1096 ms	4284 KiB

pilot

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>

using namespace std;

using ll = long long;


/**


    Score : 55/100
    Subtask 6 : 1 ≤ N, Q ≤ 10^5, Hi = i -> 9 points
    Subtask 7 : 1 ≤ N, Q ≤ 10^5, H is strictly increasing. -> 14 points
    Subtask 9: 1 ≤ N, Q ≤ 10^5 -> 11 points
    Subtask 10: 1 ≤ N, Q ≤ 10^6 -> 11 points


 */


ll create(ll node, ll l, ll r, vector<ll> &tree, vector<ll> &main_arr) {
    if (l == r) {
        tree[node] = main_arr[l];
        return tree[node];
    }


    ll mid = (l + r) / 2;

    ll left_child = create(2 * node, l, mid, tree, main_arr);
    ll right_child = create(2 * node + 1, mid + 1, r, tree, main_arr);

    tree[node] = max(left_child, right_child);
    return tree[node];

}


ll get_max(ll node, ll l, ll r, vector<ll> &tree, ll l_req, ll r_req) {
    if (l_req <= l && r <= r_req) {
        return tree[node];
    }

    if (l > r_req || r < l_req) {
        return 0;
    }

    ll mid = (l + r) / 2;
    ll left_child = get_max(2 * node, l, mid, tree, l_req, r_req);
    ll right_child = get_max(2 * node + 1, mid + 1, r, tree, l_req, r_req);

    return max(left_child, right_child);

}


void solve() {

    ll n, q;
    cin >> n >> q;
    vector<ll> list_n(n, 0);
    bool inc = true;
    for (ll i = 0; i < n; i++) {
        cin >> list_n[i];
        if (i != 0) {
            if (list_n[i - 1] > list_n[i]) {
                inc = false;
            }
        }
    }

    if (!inc) {

        vector<ll> tree(4 * n);
        create(1, 0, n - 1, tree, list_n);

        for (ll i = 0; i < q; i++) {
            ll temp;
            cin >> temp;

            ll total = 0;

            for (ll j = 0; j < n; j++) {
                if (list_n[j] > temp) {
                    continue;
                }

                ll l = j;
                ll r = n;

                while (l + 1 < r) {
                    ll mid = (l + r) / 2;

                    if (get_max(1, 0, n - 1, tree, l, mid) <= temp) {
                        l = mid;
                    } else {
                        r = mid;
                    }
                    //cout << l << " " << r;
                }
                total += l - j + 1;

            }

            cout << total << endl;


        }
        return;
    }else{

        for(ll i = 0; i < q; i++){
            ll temp;
            cin >> temp;

            if(temp < list_n[0]){
                cout << 0 << endl;
                continue;
            }

            ll l = 0;
            ll r = n;
            while(l + 1 < r){
                ll mid = (l + r)/2;
                if(list_n[mid] <= temp){
                    l = mid;
                }else{
                    r = mid;
                }
            }

            cout << ((l + 1) * (l + 2))/2 << endl;

        }

    }

}

bool single = true;

signed main() {

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if (!single) cin >> t;

    while (t--) {
        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: 0 / 11
• Subtask 10: 0 / 11