Submission #894337

#	Time	Username	Problem	Language	Result	Execution time	Memory
894337		vjudge1	Index (COCI21_index)	C++17	110 / 110	908 ms	11088 KiB

index

#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);
}
void inc(ll i) {
    add(a[i],1);
}
ll answer() {
    ll l = 1, r = N;
    while(l + 1 < r) {
        ll mid = l + r >> 1LL;
        if(check(mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    return 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] = answer();
}
for(ll i = 1; i<=qq; i++) {
    cout<<ans[i]<<"\n";
}
return 0;
}
// equal, min, max, 1, random, build
/*

*/

Compilation message (stderr)

index.cpp: In function 'long long int answer()':
index.cpp:58:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         ll mid = l + r >> 1LL;
      |                  ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50