# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1082841 |
2024-09-01T17:57:31 Z |
ShaShi |
Index (COCI21_index) |
C++17 |
|
1500 ms |
152148 KB |
#include <bits/stdc++.h>
// #define int long long
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
const int MAXN = (int)2e5 + 7;
const int MOD = 998244353;
const int INF = (int)1e9 + 7;
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], h[MAXN], res[MAXN];
vector<int> vec[MAXN];
/* Presistent SegTree */
#define mid ((l+r)>>1)
struct Node {
int val; Node *l, *r;
Node(int x) {
val = x; l = r = NULL;
}
Node(Node *ll, Node *rr) {
l = ll; r = rr;
if (l) val += l->val;
if (r) val += r->val;
}
Node(Node *node) {
val = node->val; l = node->l; r = node->r;
}
};
Node *build(int l=0, int r=n) {
if (l+1 == r) return new Node(0);
return new Node(build(l, mid), build(mid, r));
}
Node *upd(Node *node, int ind, int l=0, int r=n) {
if (l+1 == r) return new Node((node->val)+1);
if (ind < mid) return new Node(upd(node->l, ind, l, mid), node->r);
return new Node(node->l, upd(node->r, ind, mid, r));
}
int get(Node *node, int s, int t, int l=0, int r=n) {
if (s >= t) return 0;
if (s <= l && t >= r) return node->val;
if (t <= mid) return get(node->l, s, t, l, mid);
if (s >= mid) return get(node->r, s, t, mid, r);
return get(node->l, s, t, l, mid)+get(node->r, s, t, mid, r);
}
/* Presistent SegTree */
Node *seg[MAXN];
int32_t main() {
#ifdef LOCAL
freopen("inp.in", "r", stdin);
freopen("res.out", "w", stdout);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> n >> q;
for (int i=1; i<=n; i++) {
cin >> arr[i];
vec[arr[i]].pb(i);
}
seg[0] = build();
for (int i=1; i<MAXN; i++) {
seg[i] = new Node(seg[i-1]);
for (int u:vec[i]) seg[i] = upd(seg[i], u-1);
}
while (q--) {
cin >> u >> v;
int l = 1, r = v-u+2;
while (r-l > 1) {
if (v-u+1-get(seg[mid-1], u-1, v) >= mid) l = mid;
else r = mid;
}
cout << l << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
13404 KB |
Output is correct |
2 |
Correct |
9 ms |
13212 KB |
Output is correct |
3 |
Correct |
9 ms |
13400 KB |
Output is correct |
4 |
Correct |
10 ms |
13400 KB |
Output is correct |
5 |
Correct |
10 ms |
13404 KB |
Output is correct |
6 |
Correct |
9 ms |
13400 KB |
Output is correct |
7 |
Correct |
10 ms |
13404 KB |
Output is correct |
8 |
Correct |
8 ms |
13404 KB |
Output is correct |
9 |
Correct |
9 ms |
13444 KB |
Output is correct |
10 |
Correct |
10 ms |
13404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
13404 KB |
Output is correct |
2 |
Correct |
9 ms |
13212 KB |
Output is correct |
3 |
Correct |
9 ms |
13400 KB |
Output is correct |
4 |
Correct |
10 ms |
13400 KB |
Output is correct |
5 |
Correct |
10 ms |
13404 KB |
Output is correct |
6 |
Correct |
9 ms |
13400 KB |
Output is correct |
7 |
Correct |
10 ms |
13404 KB |
Output is correct |
8 |
Correct |
8 ms |
13404 KB |
Output is correct |
9 |
Correct |
9 ms |
13444 KB |
Output is correct |
10 |
Correct |
10 ms |
13404 KB |
Output is correct |
11 |
Correct |
217 ms |
44416 KB |
Output is correct |
12 |
Correct |
206 ms |
44368 KB |
Output is correct |
13 |
Correct |
227 ms |
44312 KB |
Output is correct |
14 |
Correct |
202 ms |
44332 KB |
Output is correct |
15 |
Correct |
209 ms |
44456 KB |
Output is correct |
16 |
Correct |
203 ms |
44416 KB |
Output is correct |
17 |
Correct |
205 ms |
44368 KB |
Output is correct |
18 |
Correct |
209 ms |
44372 KB |
Output is correct |
19 |
Correct |
204 ms |
44468 KB |
Output is correct |
20 |
Correct |
218 ms |
44372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
13404 KB |
Output is correct |
2 |
Correct |
9 ms |
13212 KB |
Output is correct |
3 |
Correct |
9 ms |
13400 KB |
Output is correct |
4 |
Correct |
10 ms |
13400 KB |
Output is correct |
5 |
Correct |
10 ms |
13404 KB |
Output is correct |
6 |
Correct |
9 ms |
13400 KB |
Output is correct |
7 |
Correct |
10 ms |
13404 KB |
Output is correct |
8 |
Correct |
8 ms |
13404 KB |
Output is correct |
9 |
Correct |
9 ms |
13444 KB |
Output is correct |
10 |
Correct |
10 ms |
13404 KB |
Output is correct |
11 |
Correct |
217 ms |
44416 KB |
Output is correct |
12 |
Correct |
206 ms |
44368 KB |
Output is correct |
13 |
Correct |
227 ms |
44312 KB |
Output is correct |
14 |
Correct |
202 ms |
44332 KB |
Output is correct |
15 |
Correct |
209 ms |
44456 KB |
Output is correct |
16 |
Correct |
203 ms |
44416 KB |
Output is correct |
17 |
Correct |
205 ms |
44368 KB |
Output is correct |
18 |
Correct |
209 ms |
44372 KB |
Output is correct |
19 |
Correct |
204 ms |
44468 KB |
Output is correct |
20 |
Correct |
218 ms |
44372 KB |
Output is correct |
21 |
Correct |
1355 ms |
152028 KB |
Output is correct |
22 |
Correct |
1376 ms |
151940 KB |
Output is correct |
23 |
Correct |
1410 ms |
152084 KB |
Output is correct |
24 |
Correct |
1423 ms |
152148 KB |
Output is correct |
25 |
Correct |
1410 ms |
152144 KB |
Output is correct |
26 |
Correct |
1367 ms |
152148 KB |
Output is correct |
27 |
Correct |
1403 ms |
152144 KB |
Output is correct |
28 |
Correct |
1458 ms |
152140 KB |
Output is correct |
29 |
Correct |
1500 ms |
152052 KB |
Output is correct |
30 |
Correct |
1398 ms |
152024 KB |
Output is correct |