| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 923604 |
2024-02-07T13:31:21 Z |
Isam |
Index (COCI21_index) |
C++17 |
|
2500 ms |
5468 KB |
#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
const int sz = 200001;
int n, Q, c[sz], tree[sz << 2], ans[sz];
struct query{
int l, r, index;
} q[sz];
bool cmp(query a, query b){
if(a.l ^ b.l) return a.l < b.l;
return a.r < b.r;
}
inline void update(int l, int r, int node, int x, int val){
if(l > r || l > x || r < x) return;
if(l == r){
tree[node] += val;
return;
}
int mid = l + ((r - l) >> 1);
update(l, mid, node << 1, x, val);
update(mid + 1, r, node << 1 | 1, x, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
return;
}
int get(int l, int r, int node, int L, int R){
if(l > r || l > R || r < L) return 0;
if(l >= L && r <= R) return tree[node];
int mid = l + ((r - l) >> 1);
return get(l, mid, node << 1, L, R) + get(mid + 1, r, node << 1 | 1, L, R);
}
inline void add(int x){
update(1, n, 1, x, 1);
return;
}
inline void del(int x){
update(1, n, 1, x, -1);
return;
}
int main(){
speed;
cin >> n >> Q;
for(register int i = 1; i <= n; ++i){
cin >> c[i];
}
for(register int i = 1; i <= Q; ++i){
cin >> q[i].l >> q[i].r, q[i].index = i;
}
sort(q+1,q+Q+1,cmp);
int l(1), r(0);
for(register int i = 1; i <= Q; ++i){
while(r < q[i].r) add(c[++r]);
while(r > q[i].r) del(c[r--]);
while(l < q[i].l) del(c[l++]);
while(l > q[i].l) add(c[--l]);
int L(1), R{r - l + 1}, mid, best;
while(L <= R){
mid = L + ((R - L) >> 1);
if(get(1, n, 1, mid, n) >= mid){
best = mid, L = mid + 1;
}else{
R = mid - 1;
}
}
ans[q[i].index] = best;
}
for(register int i = 1; i <= Q; ++i){
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
index.cpp: In function 'int main()':
index.cpp:55:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
55 | for(register int i = 1; i <= n; ++i){
| ^
index.cpp:58:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
58 | for(register int i = 1; i <= Q; ++i){
| ^
index.cpp:63:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
63 | for(register int i = 1; i <= Q; ++i){
| ^
index.cpp:79:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
79 | for(register int i = 1; i <= Q; ++i){
| ^
index.cpp:77:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | ans[q[i].index] = best;
| ~~~~~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 11 |
Execution timed out |
2538 ms |
5468 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 11 |
Execution timed out |
2538 ms |
5468 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
