# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
894299 |
2023-12-28T04:13:41 Z |
vjudge1 |
Index (COCI21_index) |
C++17 |
|
841 ms |
3048 KB |
#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define ull unsigned long long
#define ld long double
#define lv v+v
#define rv v+v+1
#define files freopen("expert.in", "r", stdin), freopen("expert.out", "w", stdout)
using namespace std;
const ll mod = 1e9 + 7;
const ll N = 5e4 + 10;
const ll P = 337ll;
const ld EPS = 1e-9;
const ll block = 228;
ll n,qq,a[N],ans[N], t[200000 + 10], MAXNUM=0, MINNUM = LLONG_MAX,cur = 0,l=0,r=0;
struct ask {
ll L, R, idx;
};
ask q[N];
bool cmp(ask x, ask y) {
if(x.L / block == y.L / block){return x.R < y.R;}
else {return x.L < y.L;}
}
ll sum(ll k) {
ll s = 0;
while (k >= MINNUM) {
s += t[k];
k -= k&-k;
}
return s;
}
void add(ll k, ll val) {
if(k<1) {
return;
}
while (k <= MAXNUM) {
t[k] += val;
k += k&-k;
}
}
bool check(ll t) {
ll num = sum(MAXNUM) - sum(t-1);
return num>=t;
}
void del(ll i) {
add(a[i],-1);
ll l = 1, r = N;
while(l + 1 < r) {
ll mid = l + r >> 1LL;
if(check(mid)) {
l = mid;
}
else {
r = mid;
}
}
cur = l;
}
void inc(ll i) {
add(a[i],1);
ll l = 1, r = N;
while(l + 1 < r) {
ll mid = l + r >> 1LL;
if(check(mid)) {
l = mid;
}
else {
r = mid;
}
}
cur = l;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>qq;
for(ll i = 1; i<=n; i++) {
cin>>a[i];
MAXNUM = max(MAXNUM, a[i]);
MINNUM = min(MINNUM, a[i]);
}
for(ll i = 1; i<=qq; i++) {
ll l,r;
cin>>l>>r;
q[i].L = l;
q[i].R = r;
q[i].idx = i;
}
sort(q+1, q+1+qq, cmp);
for(ll i = 1; i<=qq;i++) {
while(l < q[i].L){
del(l++);
}
while(l > q[i].L){
inc(--l);
}
while(r < q[i].R){
inc(++r);
}
while(r > q[i].R){
del(r--);
}
ans[q[i].idx] = cur;
}
for(ll i = 1; i<=qq; i++) {
cout<<ans[i]<<"\n";
}
return 0;
}
// equal, min, max, 1, random, build
/*
*/
Compilation message
index.cpp: In function 'void del(long long int)':
index.cpp:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | ll mid = l + r >> 1LL;
| ~~^~~
index.cpp: In function 'void inc(long long int)':
index.cpp:67:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | ll mid = l + r >> 1LL;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
500 KB |
Output is correct |
2 |
Correct |
6 ms |
348 KB |
Output is correct |
3 |
Correct |
6 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
524 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
500 KB |
Output is correct |
2 |
Correct |
6 ms |
348 KB |
Output is correct |
3 |
Correct |
6 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
524 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
766 ms |
3044 KB |
Output is correct |
12 |
Correct |
809 ms |
3048 KB |
Output is correct |
13 |
Correct |
748 ms |
3044 KB |
Output is correct |
14 |
Correct |
745 ms |
3044 KB |
Output is correct |
15 |
Correct |
752 ms |
3044 KB |
Output is correct |
16 |
Correct |
841 ms |
3044 KB |
Output is correct |
17 |
Correct |
839 ms |
3044 KB |
Output is correct |
18 |
Correct |
835 ms |
3048 KB |
Output is correct |
19 |
Correct |
764 ms |
3044 KB |
Output is correct |
20 |
Correct |
754 ms |
3044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
500 KB |
Output is correct |
2 |
Correct |
6 ms |
348 KB |
Output is correct |
3 |
Correct |
6 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
6 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
6 ms |
524 KB |
Output is correct |
10 |
Correct |
6 ms |
348 KB |
Output is correct |
11 |
Correct |
766 ms |
3044 KB |
Output is correct |
12 |
Correct |
809 ms |
3048 KB |
Output is correct |
13 |
Correct |
748 ms |
3044 KB |
Output is correct |
14 |
Correct |
745 ms |
3044 KB |
Output is correct |
15 |
Correct |
752 ms |
3044 KB |
Output is correct |
16 |
Correct |
841 ms |
3044 KB |
Output is correct |
17 |
Correct |
839 ms |
3044 KB |
Output is correct |
18 |
Correct |
835 ms |
3048 KB |
Output is correct |
19 |
Correct |
764 ms |
3044 KB |
Output is correct |
20 |
Correct |
754 ms |
3044 KB |
Output is correct |
21 |
Runtime error |
4 ms |
1368 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |