Submission #1094125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094125		0pt1mus23	Index (COCI21_index)	C++14	110 / 110	1085 ms	14892 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define needforspeed ios::sync_with_stdio(0);cin.tie(0);
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
const int mod = 1e9 +7,sze = 2e5 +23,inf = INT_MAX, L = 31; 
int block; 

int fener(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){
    int x = a.first.first / block,y = b.first.first / block;
    if(x!=y){
        return a.first.first < b.first.first;
    }
    return a.first.second < b.first.second;
}
int tot =0;
int T[sze+23];
void upd(int node,int v){
    node++;
    while(node<=sze){
        T[node]+=v;
        node +=(node & -node);
    }
}
int qry2(int node){
    int sum=0;
    node++;
    while(node>0){
        sum+=T[node];
        node -= (node & -node);
    }
    return sum;
}

int qry(int node){
    return qry2(sze) - qry2(node -1);
}

void ekle(int v){
    tot+=v;
    upd(v,1);
    // cout<<"ekle: "<<v<<endl;

}
void sil(int v){
    tot-=v;
    upd(v,-1);
    // cout<<"sil: "<<v<<endl;
}
void opt1z(){
    int n,q;
    cin>>n>>q;
    block = ceil(sqrt(n));
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int> ans(q);

    vector<pair<pair<int,int>,int>> qq;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;l--;r--;
        qq.pb({{l,r},i});
    }
    sort(all(qq),fener);
    int cl = 0;
    int cr = -1;

    for(int i=0;i<q;i++){
        int l=qq[i].first.first;
        int r=qq[i].first.second;
        int idx = qq[i].second;

        while(cl>l){
            cl--;
            ekle(arr[cl]);
        }
        while(cr<r){
            cr++;
            ekle(arr[cr]);
        }
        while(cl<l){
            sil(arr[cl]);
            cl++;
        }
        while(cr>r){
            sil(arr[cr]);
            cr--;
        }
        int lx=1;
        int rx = r-l+1;
        int a=1;
        while(lx<=rx){
            int mid = (lx+rx)/2;
            // cout<<mid<<endl;
            if(qry(mid) >=mid){
                a=mid;
                lx = mid+1;
            }
            else{
                rx = mid-1;
            }
        }
        ans[idx]=a;
    }


    for(int i=0;i<q;i++) cout<<ans[i]<<endl;
}
 
signed main() {
    needforspeed;
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

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