Submission #867788

#	Time	Username	Problem	Language	Result	Execution time	Memory
867788		sleepntsheep	Pilot (NOI19_pilot)	C++14	3 / 100	54 ms	15440 KiB

pilot

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 1000005

int n, q, c[N];
array<int, 2> a[N], b[N];
set<int> s;
ll z;
ll C2(ll x) { return x*(x+1)/2; }

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i][0], a[i][1] = i;
    for (int i = 0; i < q; ++i) cin >> b[i][0], b[i][1] = i;
    sort(a, a+n);
    sort(b, b+q);
    s.emplace(-1); s.emplace(n); z = C2(n);
    for (int i = q, j = n - 1; i--;)
    {
        for (; j >= 0 && a[j][0] > b[i][0]; --j)
        {
            auto it = s.upper_bound(a[j][1]);
            ll r = *it, l = *prev(it), w = (r-l-1), wl=a[j][1]-l-1, wr =r-a[j][1]-1;
            z += -C2(w) + C2(wl) + C2(wr);
            s.insert(a[j][1]);
        }
        c[i] = z;
    }
    for (int i = 0; i < q; ++i) cout << c[i] << '\n';


    return 0;
}

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