Submission #1313875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313875		sadraallami	Index (COCI21_index)	C++20	60 / 110	2597 ms	109000 KiB

index

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> mat;
typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define lc 2*id
#define rc 2*id+1
#define pb push_back
#define all(x) x.begin(),x.end()
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define print(n) for(ll i:n){cout << i << ' ';}cout << endl;
ll pw(ll a,ll b,ll md=998244353){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}
const int maxn=5e5+50;
const ll mod=998244353;
const ll sq=330;
const ll lg=22;
const ll inf=2e18;
vector<ll> adj[maxn],add[maxn],ar[maxn];
int vis[maxn];
ll li[maxn],res[maxn],seg[4*maxn],a[maxn],b[maxn];
ll n,q;
vector<ll> vec;
set<ll> st;
void build(ll l,ll r,ll id){
    if(l==r){
        seg[id]=1;
        return ;
    }
    ll mid=(l+r)/2;
    build(l,mid,lc);
    build(mid+1,r,rc);
    seg[id]=seg[lc]+seg[rc];
}
void upd(ll l,ll r,ll p,ll id){
    if(l>p || r<p)return ;
    if(l==r){
        seg[id]=0;
        return ;
    }
    ll mid=(l+r)/2;
    upd(l,mid,p,lc);
    upd(mid+1,r,p,rc);
    seg[id]=seg[lc]+seg[rc];
}
ll get(ll l,ll r,ll s,ll e,ll id){
    if(l>e || r<s)return 0;
    if(l>=s && r<=e)return seg[id];
    ll mid=(l+r)/2;
    return get(l,mid,s,e,lc)+get(mid+1,r,s,e,rc);
}
void solve(){
    vec.clear();
    for(ll i:st){
        if(st.upper_bound(i)!=st.end()){
            ll x=*st.upper_bound(i);
            if(x-i>1)vec.pb((x+i)/2);
        }
    }
    for(ll i:vec){
        st.insert(i);
    }
    //print(vec);
    for(ll i=1;i<=q;i++){
        ll x=*st.upper_bound(res[i]);
        add[x].pb(i);
    }
    build(1,n,1);
    for(ll i=1;i<=n;i++){
        if(upper_bound(all(vec),li[i])!=vec.end()){
            ll x=*upper_bound(all(vec),li[i]);
            ar[x].pb(i);
            //cout<< i << " --> " << x << endl;
        }
    }
    for(ll i:vec){
        for(ll j:ar[i])upd(1,n,j,1);
        for(ll j:add[i]){
            if(get(1,n,a[j],b[j],1)>=i)res[j]=i;
        }
    }

}
int main(){
    fast;
    cin>>n>>q;
    for(ll i=1;i<=n;i++){
        cin>>li[i];
    }
    for(ll i=1;i<=q;i++){
        cin>>a[i]>>b[i];
    }
    st.insert(0);st.insert(n+1);
    for(ll i=1;i<=lg;i++){
        solve();
    }
    for(ll i=1;i<=q;i++)cout<< res[i] << endl;
}

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