#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = (int)2e5 + 5;
const int M = 450;
int n, a[N], f[N], m, ans[N];
struct que{
int l, r, idx;
};
bool cmp(const que &a, const que &b)
{
if (a.l / M != b.l / M)
return a.l < b.l;
else return a.r < b.r;
}
void upd(int x, int val)
{
for(int i = x; i < N; i += i & -i) f[i] += val;
}
int get(int x)
{
int res = 0;
for(int i = x; i > 0; i -= i & -i) res += f[i];
return res;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
vector< que > queries;
for(int i = 1; i <= m; i++)
{
int l, r;
cin >> l >> r;
queries.pb({l, r, i});
}
sort(all(queries), cmp);
int cur_l = 1, cur_r = 0;
for(auto [l, r, nom] : queries)
{
while(cur_l > l)
{
cur_l--;
upd(a[cur_l], 1);
}
while(cur_r < r)
{
cur_r++;
upd(a[cur_r], 1);
}
while(cur_l < l)
{
upd(a[cur_l], -1);
cur_l++;
}
while(cur_r > r)
{
upd(a[cur_r], -1);
cur_r--;
}
int L = 1, R = r - l + 1;
while(L < R)
{
int m = (L + R + 1) >> 1;
if (get(N - 1) - get(m - 1) >= m) L = m;
else R = m - 1;
}
ans[nom] = L;
}
for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
Compilation message
index.cpp: In function 'int main()':
index.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | for(auto [l, r, nom] : queries)
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
200 ms |
2740 KB |
Output is correct |
12 |
Correct |
215 ms |
2744 KB |
Output is correct |
13 |
Correct |
214 ms |
2724 KB |
Output is correct |
14 |
Correct |
197 ms |
2728 KB |
Output is correct |
15 |
Correct |
215 ms |
2724 KB |
Output is correct |
16 |
Correct |
203 ms |
2728 KB |
Output is correct |
17 |
Correct |
199 ms |
2732 KB |
Output is correct |
18 |
Correct |
198 ms |
2728 KB |
Output is correct |
19 |
Correct |
238 ms |
2720 KB |
Output is correct |
20 |
Correct |
198 ms |
2728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
200 ms |
2740 KB |
Output is correct |
12 |
Correct |
215 ms |
2744 KB |
Output is correct |
13 |
Correct |
214 ms |
2724 KB |
Output is correct |
14 |
Correct |
197 ms |
2728 KB |
Output is correct |
15 |
Correct |
215 ms |
2724 KB |
Output is correct |
16 |
Correct |
203 ms |
2728 KB |
Output is correct |
17 |
Correct |
199 ms |
2732 KB |
Output is correct |
18 |
Correct |
198 ms |
2728 KB |
Output is correct |
19 |
Correct |
238 ms |
2720 KB |
Output is correct |
20 |
Correct |
198 ms |
2728 KB |
Output is correct |
21 |
Correct |
879 ms |
10004 KB |
Output is correct |
22 |
Correct |
872 ms |
10004 KB |
Output is correct |
23 |
Correct |
869 ms |
9988 KB |
Output is correct |
24 |
Correct |
872 ms |
10000 KB |
Output is correct |
25 |
Correct |
899 ms |
10000 KB |
Output is correct |
26 |
Correct |
849 ms |
10032 KB |
Output is correct |
27 |
Correct |
895 ms |
9996 KB |
Output is correct |
28 |
Correct |
870 ms |
9992 KB |
Output is correct |
29 |
Correct |
848 ms |
9996 KB |
Output is correct |
30 |
Correct |
936 ms |
9992 KB |
Output is correct |