#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct MergeSortTree {
vector<vi> s;
void buildFullTree() {
for (int i = sz(s)/2-1; i > 0; i--) {
s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
}
}
int countGreater(int l, int r, int k) {
int output = 0;
for (l += sz(s)/2, r += sz(s)/2; l < r; l /= 2, r /= 2) {
if (l&1) output += s[l].end() - upper_bound(all(s[l]), k), l++;
if (r&1) --r, output += s[r].end() - upper_bound(all(s[r]), k);
}
return output;
}
};
int N, Q;
MergeSortTree tree;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> Q; tree.s.resize(2*N, vi(0));
FOR(i, 0, N) {
int a; cin >> a; tree.s[N+i] = {a};
}
tree.buildFullTree();
FOR(query, 0, Q) {
int l, r; cin >> l >> r;
int works = -1;
for (int move = r-l+1; move > 0; move /= 2) {
if (tree.countGreater(l-1, r, works+move-1) >= works+move) works += move;
}
cout << works << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
