oj.uz

Submission #894305

# Submission time Handle Problem Language Result Execution time Memory
894305 2023-12-28T04:21:47 Z vjudge1 Index (COCI21_index) C++17
60 / 110
 2500 ms 9808 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 = 2e5 + 10;
const ll P = 337ll;
const ld EPS = 1e-9;
const ll block = 450;
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);
    if(a[i] < cur) {
        return;
    }
    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);
    if(a[i] < cur) {
        return;
    }
    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:56:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         ll mid = l + r >> 1LL;
      |                  ~~^~~
index.cpp: In function 'void inc(long long int)':
index.cpp:73:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         ll mid = l + r >> 1LL;
      |                  ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2404 KB Output is correct
2 Correct 5 ms 2520 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 5 ms 2568 KB Output is correct
7 Correct 5 ms 2568 KB Output is correct
8 Correct 5 ms 2392 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2404 KB Output is correct
2 Correct 5 ms 2520 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 5 ms 2568 KB Output is correct
7 Correct 5 ms 2568 KB Output is correct
8 Correct 5 ms 2392 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 1033 ms 5440 KB Output is correct
12 Correct 1055 ms 5440 KB Output is correct
13 Correct 998 ms 5444 KB Output is correct
14 Correct 1000 ms 5436 KB Output is correct
15 Correct 1012 ms 5448 KB Output is correct
16 Correct 1133 ms 5436 KB Output is correct
17 Correct 1147 ms 5456 KB Output is correct
18 Correct 1155 ms 5636 KB Output is correct
19 Correct 1004 ms 5468 KB Output is correct
20 Correct 1038 ms 5688 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2404 KB Output is correct
2 Correct 5 ms 2520 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 5 ms 2568 KB Output is correct
7 Correct 5 ms 2568 KB Output is correct
8 Correct 5 ms 2392 KB Output is correct
9 Correct 4 ms 2392 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 1033 ms 5440 KB Output is correct
12 Correct 1055 ms 5440 KB Output is correct
13 Correct 998 ms 5444 KB Output is correct
14 Correct 1000 ms 5436 KB Output is correct
15 Correct 1012 ms 5448 KB Output is correct
16 Correct 1133 ms 5436 KB Output is correct
17 Correct 1147 ms 5456 KB Output is correct
18 Correct 1155 ms 5636 KB Output is correct
19 Correct 1004 ms 5468 KB Output is correct
20 Correct 1038 ms 5688 KB Output is correct
21 Execution timed out 2519 ms 9808 KB Time limit exceeded
22 Halted 0 ms 0 KB -