165832025-05-06 18:36:20algoproTornyokcpp17Wrong answer 46/100347ms16884 KiB
// UUID: 3c4fa843-8cfa-4f4d-a164-eea66205858b
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5, MAXK = 1e6 + 1, INF = 2e9;

int n, k, b[MAXN], h[MAXK], s[MAXN];
array<int, 2> vans[MAXN];

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < k; i++) cin >> h[i];
    b[n] = INF;

    s[0] = INF + 1;
    int sp = 0, vansp = -1;
    for (int x : b) {
        int i = 1;
        while (s[sp] <= x) {
            vans[++vansp] = {s[sp], i};
            sp--;
            i++;
        }
        s[++sp] = x;
    }

    vans[++vansp] = {0, 0};
    vans[++vansp] = {INF, 0};
    sort(vans, vans + vansp + 1);

    for (int i = 1; i <= vansp; i++) {
        vans[i][1] = max(vans[i][1], vans[i - 1][1]);
    }
    for (int i = 0; i < k; i++) {
        int l = -1, r = vansp + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (vans[m][0] >= h[i]) {
                r = m;
            } else {
                l = m;
            }
        }
        cout << vans[l][1] << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base46/100
1Accepted0/0101ms8244 KiB
2Wrong answer0/0293ms12084 KiB
3Accepted2/2100ms8244 KiB
4Accepted2/2103ms8256 KiB
5Accepted6/6101ms8440 KiB
6Wrong answer0/6101ms8428 KiB
7Wrong answer0/4111ms8452 KiB
8Wrong answer0/4125ms8500 KiB
9Accepted8/8202ms9776 KiB
10Accepted8/8194ms12084 KiB
11Wrong answer0/5279ms11572 KiB
12Wrong answer0/5300ms12084 KiB
13Accepted5/5134ms9012 KiB
14Accepted5/5178ms10676 KiB
15Accepted5/5207ms12428 KiB
16Wrong answer0/5284ms11316 KiB
17Wrong answer0/5312ms12084 KiB
18Wrong answer0/5344ms12592 KiB
19Wrong answer0/5347ms12852 KiB
20Wrong answer0/5252ms16652 KiB
21Wrong answer0/5252ms16640 KiB
22Accepted5/5236ms16884 KiB