#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
#define N 200001
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
int ans[N], l[N], r[N];
const int BL = 450;
int l1, l2;
bool cmp(int &x, int &y)
{
l1 = l[x] / BL;
l2 = l[y] / BL;
if (l1 != l2)
return l1 < l2;
if (l1 & 1)
return r[x] > r[y];
return r[x] < r[y];
}
const int NN = 200001;
int t[NN];
void add(int v)
{
for (; v < NN; v = v | (v + 1))
t[v]++;
}
void del(int v)
{
for (; v < NN; v = v | (v + 1))
t[v]--;
}
int res;
void get(int v)
{
res = 0;
for (; v >= 0; v = (v & (v + 1)) - 1)
res += t[v];
}
int main()
{
istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int n, q, i;
cin >> n >> q;
int a[n];
for (i = 0; i < n; i++)
cin >> a[i];
vector <int> vr; vr.clear();
for (i = 0; i < q; i++)
{
cin >> l[i] >> r[i];
l[i]--; r[i]--;
vr.PB(i);
}
sort(all(vr), cmp);
int ll = 0, rr = -1, all, L, R, md;
for (i = 0; i < sz(vr); i++)
{
while (rr < r[vr[i]])
add(a[++rr]);
while (l[vr[i]] < ll)
add(a[--ll]);
while (r[vr[i]] < rr)
del(a[rr--]);
while (ll < l[vr[i]])
del(a[ll++]);
all = rr - ll + 1;
L = 0; R = all;
while (L < R)
{
md = (L + R + 1) >> 1;
get(md - 1);
if (all - res >= md)
L = md;
else R = md - 1;
}
ans[vr[i]] = L;
}
for (i = 0; i < q; i++)
pri(ans[i]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
3 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
3 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
168 ms |
2720 KB |
Output is correct |
12 |
Correct |
170 ms |
2724 KB |
Output is correct |
13 |
Correct |
165 ms |
2668 KB |
Output is correct |
14 |
Correct |
173 ms |
2764 KB |
Output is correct |
15 |
Correct |
175 ms |
2724 KB |
Output is correct |
16 |
Correct |
171 ms |
2736 KB |
Output is correct |
17 |
Correct |
177 ms |
2724 KB |
Output is correct |
18 |
Correct |
176 ms |
2724 KB |
Output is correct |
19 |
Correct |
166 ms |
2716 KB |
Output is correct |
20 |
Correct |
172 ms |
2712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
3 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
336 KB |
Output is correct |
5 |
Correct |
2 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
2 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
336 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
168 ms |
2720 KB |
Output is correct |
12 |
Correct |
170 ms |
2724 KB |
Output is correct |
13 |
Correct |
165 ms |
2668 KB |
Output is correct |
14 |
Correct |
173 ms |
2764 KB |
Output is correct |
15 |
Correct |
175 ms |
2724 KB |
Output is correct |
16 |
Correct |
171 ms |
2736 KB |
Output is correct |
17 |
Correct |
177 ms |
2724 KB |
Output is correct |
18 |
Correct |
176 ms |
2724 KB |
Output is correct |
19 |
Correct |
166 ms |
2716 KB |
Output is correct |
20 |
Correct |
172 ms |
2712 KB |
Output is correct |
21 |
Correct |
803 ms |
10056 KB |
Output is correct |
22 |
Correct |
783 ms |
10016 KB |
Output is correct |
23 |
Correct |
835 ms |
9988 KB |
Output is correct |
24 |
Correct |
770 ms |
9992 KB |
Output is correct |
25 |
Correct |
811 ms |
9996 KB |
Output is correct |
26 |
Correct |
827 ms |
9992 KB |
Output is correct |
27 |
Correct |
833 ms |
9988 KB |
Output is correct |
28 |
Correct |
784 ms |
9988 KB |
Output is correct |
29 |
Correct |
763 ms |
10044 KB |
Output is correct |
30 |
Correct |
800 ms |
9996 KB |
Output is correct |