Submission #949745

#	Time	Username	Problem	Language	Result	Execution time	Memory
949745		blackavar	Index (COCI21_index)	C++14	60 / 110	2577 ms	55980 KiB

index

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

const int offset = (1 << 18);

struct st{
    vector <long long> vec[offset * 2];

    void insert (long long a, long long b) {
        a += offset;
        while (a) {
            vec[a].push_back(b);
            a /= 2;
        }
    }

    void init() {
        for (int i = 0; i < offset * 2; i++) sort(vec[i].begin(), vec[i].end());
    }

    long long get(long long id, long long l, long long r, long long a, long long b, long long x) {
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return (lower_bound(vec[id].begin(), vec[id].end(), x)) - vec[id].begin();

        long long mid = (l + r) / 2;
        return get(id * 2, l, mid, a, b, x) + get(id * 2 + 1, mid + 1, r, a, b, x);
    }
}segTree;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, q;
    cin >> n >> q;
    long long a[n + 1];
    for (int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        a[i] = x;
        segTree.insert(i, x);
    }
    segTree.init();
    while (q--) {
        long long l, r;
        cin >> l >> r;
        long long lo = 1, hi = 1e9, res = -1;
        while (lo <= hi) {
            long long mid = lo + (hi - lo) / 2;
            long long cntx = r - l + 1 - segTree.get(1, 0, offset - 1, l, r, mid);
            if (cntx >= mid) {
                lo = mid + 1;
                res = mid;
            }
            else hi = mid - 1;
        }
        cout << res << "\n";
    }
    return 0;
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:37:15: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   37 |     long long a[n + 1];
      |               ^

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