#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct segment {
const int dim = 1 << 18;
struct node {
vector<int> v;
};
vector<node> s = vector<node>(2 * dim);
void upd(int pos, int l, int r, int p, int val) {
if (p < l || r < p) return;
s[pos].v.pb(val);
if (l == r) return;
int m = (l + r) / 2;
upd(2 * pos, l, m, p, val);
upd(2 * pos + 1, m + 1, r, p, val);
}
void upd(int p, int val) {
upd(1, 0, dim - 1, p, val);
}
void init() {
for (auto k : s) {
sort(k.v.begin(), k.v.end());
}
}
vector<int> nodes;
void query(int pos, int l, int r, int a, int b) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
nodes.pb(pos);
return;
}
int m = (l + r) / 2;
query(2 * pos, l, m, a, b);
query(2 * pos + 1, m + 1, r, a, b);
}
int query(int a, int b) {
nodes.clear();
query(1, 0, dim - 1, a, b);
// cout << "k: ";
// for (int x : nodes) {
// for (int y : s[x].v) cout << y << " ";
// }
// cout << endl;
int l = 1, r = 1e6;
while (l < r - 1) {
int m = (l + r) / 2;
int tot = 0;
for (int i : nodes) {
tot += s[i].v.size() - (lower_bound(s[i].v.begin(), s[i].v.end(), m) - s[i].v.begin());
}
if (tot >= m)
l = m;
else
r = m;
}
return l;
}
} seg;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q;
cin >> N >> Q;
for (int i = 0; i < N; i++) {
int u;
cin >> u;
seg.upd(i, u);
}
seg.init();
for (int i = 0; i < Q; i++) {
int a, b;
cin >> a >> b;
cout << seg.query(a - 1, b - 1) << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
