Submission #1186909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186909		vusal	Pilot (NOI19_pilot)	C++20	8 / 100	1096 ms	2052 KiB

pilot

#include <bits/stdc++.h>
// author: vusal
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int oo = 1e18 + 9;
const int sz = 2e6+7;
const int MOD = 1e9+7;

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int>h(n), y(q);

    for(int &i : h) cin >> i;
    for(int &i : y) cin >> i;

    for(int he : y)
    {
        int st = 0, nd = 0, sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(h[i] <= he && i < (n - 1)) nd++;
            else
            {
                if(h[nd] > he) nd--;
                // cout << "Start: " << st << " End: " << nd << " " << "Count: ";
                // cout << ((nd - st + 1) * (nd - st + 2) / 2) << endl;
                if(nd >= st) sum += ((nd - st + 1) * (nd - st + 2) / 2);
                st = nd + 1;
                nd = nd + 1;
                while(h[st] > he && st < (n - 1)) st++, nd++;
            }
        }
        // cout << "Start: " << st << " End: " << nd << " " << "Count: ";
        // cout << ((nd - st + 1) * (nd - st + 2) / 2) << endl;
        sum += ((nd - st + 1) * (nd - st + 2) / 2);
        cout << sum  - 1 << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(int i = 1; i <= tc; i++)
    {
        //cout << "Case " << i << ":";
        solve();
    }
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 5 / 5
• Subtask 6: 0 / 9
• Subtask 7: 0 / 14
• Subtask 8: 0 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11