Submission #1134820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134820		Roumak77	Pilot (NOI19_pilot)	C++20	55 / 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;

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);

    for(ll i = 0; i < n; i++){
        cin >> list_n[i];
    }

    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;


    }


}

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: 0 / 9
• Subtask 7: 0 / 14
• Subtask 8: 10 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11