제출 #1281067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281067		flaming_top1	Index (COCI21_index)	C++20	110 / 110	1082 ms	91784 KiB

index

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n, q, idx[200005], nodes, ver[200005];
lint a[200005];
vector<int> adj[200005];
lint seg[22 * 200005], L[22 * 200005], R[22 * 200005];

int build(int l, int r)
{
    int cur = ++nodes;
    if (l == r)
    {
        seg[cur] = 0;
        return cur;
    }
    int mid = l + r >> 1;
    L[cur] = build(l, mid);
    R[cur] = build(mid + 1, r);
    return cur;
}

int update(int prev, int l, int r, int idx, int k)
{
    int cur = ++nodes;
    if (l == r)
    {
        seg[cur] = seg[prev] + k;
        return cur;
    }
    int mid = l + r >> 1;

    L[cur] = L[prev];
    R[cur] = R[prev];

    if (idx <= mid)
        L[cur] = update(L[prev], l, mid, idx, k);
    else
        R[cur] = update(R[prev], mid + 1, r, idx, k);
    seg[cur] = seg[L[cur]] + seg[R[cur]];
    return cur;
}

lint get(int nodel, int noder, int l, int r, int templ, int tempr)
{
    if (templ <= l and r <= tempr)
        return seg[noder] - seg[nodel];
    else if (r < templ or tempr < l)
        return 0;
    int mid = l + r >> 1;
    return get(L[nodel], L[noder], l, mid, templ, tempr) + get(R[nodel], R[noder], mid + 1, r, templ, tempr);
}

lint binaryu(int L, int R) // chặt nhị phân tìm chỉ số H lớn nhất
{
    int l = 1, r = R - L + 1, mid, ans = 0;
    while (l <= r)
    {
        mid = l + r >> 1;

        if (get(ver[L - 1], ver[R], 1, 200000, mid, 200000) >= mid)
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return ans;
}

fami lore()
{
    SPED;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // seg[0] = build(1, 200000);

    for (int i = 1; i <= n; i++)
        ver[i] = update(ver[i - 1], 1, 200000, a[i], 1);

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << binaryu(l, r) << endl;
    }
}
// Let your soul wander where dreams are born.

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50