# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
892083 |
2023-12-24T18:40:16 Z |
kh0i |
Index (COCI21_index) |
C++17 |
|
1687 ms |
11012 KB |
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 2e5 + 3;
struct Query{
int l, r, id;
} d[N];
struct Fenwick{
#define gb(x) (x) & -(x)
vector<ll> bit;
int n;
void init(int _n){
bit.resize(_n + 4, 0);
n = _n;
}
void upd(int x, ll val){
while(x <= n){
bit[x] += val;
x += gb(x);
}
}
ll get(int x){
ll res = 0;
while(x > 0){
res += bit[x];
x -= gb(x);
}
return res;
}
} fen;
int n, q, p[N], ans, res[N];
void add(int x){
fen.upd(p[x], 1);
if(fen.get(N) - fen.get(ans) >= ans + 1)
++ans;
}
void del(int x){
fen.upd(p[x], -1);
if(fen.get(N) - fen.get(ans - 1) < ans)
--ans;
}
void solve(){
fen.init(N);
cin >> n >> q;
for(int i = 1; i <= n; ++i)
cin >> p[i];
for(int i = 1; i <= q; ++i){
cin >> d[i].l >> d[i].r;
d[i].id = i;
}
int S = sqrt(n);
sort(d + 1, d + q + 1, [S](const Query &A, const Query &B){
return A.l / S != B.l / S ? A.l / S < B.l / S : A.r < B.r;
});
int l = 1, r = 0;
for(int i = 1; i <= q; ++i){
while(r < d[i].r) add(++r);
while(r > d[i].r) del(r--);
while(l < d[i].l) del(l++);
while(l > d[i].l) add(--l);
res[d[i].id] = ans;
}
for(int i = 1; i <= q; ++i)
cout << res[i] << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3928 KB |
Output is correct |
2 |
Correct |
2 ms |
3932 KB |
Output is correct |
3 |
Correct |
2 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
3932 KB |
Output is correct |
5 |
Correct |
2 ms |
3932 KB |
Output is correct |
6 |
Correct |
2 ms |
3932 KB |
Output is correct |
7 |
Correct |
2 ms |
3932 KB |
Output is correct |
8 |
Correct |
2 ms |
3928 KB |
Output is correct |
9 |
Correct |
2 ms |
3932 KB |
Output is correct |
10 |
Correct |
2 ms |
3932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3928 KB |
Output is correct |
2 |
Correct |
2 ms |
3932 KB |
Output is correct |
3 |
Correct |
2 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
3932 KB |
Output is correct |
5 |
Correct |
2 ms |
3932 KB |
Output is correct |
6 |
Correct |
2 ms |
3932 KB |
Output is correct |
7 |
Correct |
2 ms |
3932 KB |
Output is correct |
8 |
Correct |
2 ms |
3928 KB |
Output is correct |
9 |
Correct |
2 ms |
3932 KB |
Output is correct |
10 |
Correct |
2 ms |
3932 KB |
Output is correct |
11 |
Correct |
200 ms |
5312 KB |
Output is correct |
12 |
Correct |
199 ms |
5160 KB |
Output is correct |
13 |
Correct |
207 ms |
5312 KB |
Output is correct |
14 |
Correct |
199 ms |
5200 KB |
Output is correct |
15 |
Correct |
202 ms |
5200 KB |
Output is correct |
16 |
Correct |
203 ms |
5412 KB |
Output is correct |
17 |
Correct |
205 ms |
5312 KB |
Output is correct |
18 |
Correct |
200 ms |
5308 KB |
Output is correct |
19 |
Correct |
203 ms |
5328 KB |
Output is correct |
20 |
Correct |
201 ms |
5200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3928 KB |
Output is correct |
2 |
Correct |
2 ms |
3932 KB |
Output is correct |
3 |
Correct |
2 ms |
4104 KB |
Output is correct |
4 |
Correct |
2 ms |
3932 KB |
Output is correct |
5 |
Correct |
2 ms |
3932 KB |
Output is correct |
6 |
Correct |
2 ms |
3932 KB |
Output is correct |
7 |
Correct |
2 ms |
3932 KB |
Output is correct |
8 |
Correct |
2 ms |
3928 KB |
Output is correct |
9 |
Correct |
2 ms |
3932 KB |
Output is correct |
10 |
Correct |
2 ms |
3932 KB |
Output is correct |
11 |
Correct |
200 ms |
5312 KB |
Output is correct |
12 |
Correct |
199 ms |
5160 KB |
Output is correct |
13 |
Correct |
207 ms |
5312 KB |
Output is correct |
14 |
Correct |
199 ms |
5200 KB |
Output is correct |
15 |
Correct |
202 ms |
5200 KB |
Output is correct |
16 |
Correct |
203 ms |
5412 KB |
Output is correct |
17 |
Correct |
205 ms |
5312 KB |
Output is correct |
18 |
Correct |
200 ms |
5308 KB |
Output is correct |
19 |
Correct |
203 ms |
5328 KB |
Output is correct |
20 |
Correct |
201 ms |
5200 KB |
Output is correct |
21 |
Correct |
1641 ms |
10860 KB |
Output is correct |
22 |
Correct |
1637 ms |
10648 KB |
Output is correct |
23 |
Correct |
1624 ms |
10764 KB |
Output is correct |
24 |
Correct |
1592 ms |
10836 KB |
Output is correct |
25 |
Correct |
1682 ms |
10652 KB |
Output is correct |
26 |
Correct |
1687 ms |
10648 KB |
Output is correct |
27 |
Correct |
1629 ms |
10644 KB |
Output is correct |
28 |
Correct |
1639 ms |
10640 KB |
Output is correct |
29 |
Correct |
1645 ms |
11012 KB |
Output is correct |
30 |
Correct |
1614 ms |
10644 KB |
Output is correct |