Submission #1187042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187042		Cebrayil09	Pilot (NOI19_pilot)	C++20	78 / 100	1092 ms	3656 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

#define pii pair < int , int >
#define eb emplace_back
#define pb push_back
#define int long long
#define fi first
#define se second

const int inf = 1e18;

void solve() {
    int n,q; cin >> n >> q;
    vector < int > h(n+1), t(q+1);

    for(int i = 1;i <= n;i++) cin >> h[i];
    for(int i = 1;i <= q;i++) cin >> t[i];


    if(q == 1 && t[1] == 1e6) {
        cout << n*(n+1)/2 << "\n";
        return;
    }

    vector<int> qwe = h;
    sort(qwe.begin(), qwe.end());

    if(qwe == h) {
        for(int _ = 1;_ <= q;_++) {
            int l = 1, r = n, best = 0;
            while(l <= r) {
                int mid = l + (r-l)/2;

                if(h[mid] <= t[_]) {
                    best = mid;
                    l = mid+1;
                }
                else r = mid-1;
            }

            cout << best*(best+1)/2 << "\n";
        }
        return;
    }

    for(int _ = 1;_ <= q;_++) {
        int ans = 0, rn = 0;
        bool is = 0;

        for(int i = 1;i <= n;i++) {
            if(h[i] <= t[_]) {
                rn++;
                is = 1;
            }
            else if(is) {
                ans += rn*(rn+1)/2;
                rn = 0;
                is = 0;
            }
        }

        ans += rn*(rn+1)/2;
        cout << ans << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);

    int t = 1; //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