Submission #788743

#	Time	Username	Problem	Language	Result	Execution time	Memory
788743		Ahmed57	OGLEDALA (COI15_ogledala)	C++17	0 / 100	4029 ms	6876 KiB

ogledala

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;
long long mid = 1;
int dp[300001];
long long lim = 1e18;
vector<int> v;
long long solve(long long x){
    if(x<mid)return 0;
    if(dp[x]!=-1)return dp[x];
    v.push_back(x);
    assert(v.size()<=50);
    return dp[x]=(x<=lim?1LL:0LL)+solve(x/2)+solve((x-1)/2);
}
long long ge(long long l,long long r,int LF,int RF,long long x){
    if(r-l+1<=mid){
        return (l+r)/2;
    }
    assert(mid>=1);
    assert(((l!=LF)||(r!=RF)));
    long long len = r-l+1 ,lol = solve((len-1)/2);
    for(auto e:v)dp[e] = -1;
        v.clear();
    if(lol>=x){
        return ge(l,l+((len-1)/2)-1,l,r,x);
    }else{
        return ge(l+((len+1)/2),r,l,r,x-lol);
    }
}
signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    memset(dp,-1,sizeof dp);
    long long m,n,q;
    cin>>m>>n>>q;
    long long arr[n+2];
    arr[0] = 0;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    arr[n+1] = m+1;
    for(int i = 0;i<=n;i++){
        assert(arr[i+1]>arr[i]);
    }
    z:while(q--){
        long long x;cin>>x;
        if(x<=n){
            cout<<arr[x]<<endl;
            continue;
        }
        x-=n;
        long long l=1,r=1e18 , ans = 0;
        lim = 1e18;
        while(l<=r){
            mid = (l+r)/2;
            assert(mid>=1);
            for(auto e:v)dp[e] = -1;
            v.clear();
            long long all = 0;
            for(int i = 0;i<=n;i++){
                all+=solve(arr[i+1]-arr[i]-1);
                for(auto e:v)dp[e] = -1;
                v.clear();
            }
            if(all>=x){
                ans = mid;
                l = mid+1;
            }else r = mid-1;
        }
        assert(ans!=0);
        for(auto e:v)dp[e] = -1;
        v.clear();
        mid = ans+1;
        assert(mid>=1);
        for(int i = 0;i<=n;i++){
            x-=solve(arr[i+1]-arr[i]-1);
            for(auto e:v)dp[e] = -1;
            v.clear();
        }
        assert(x>=1);
        for(auto e:v)dp[e] = -1;
        v.clear();
        mid = ans;
        lim = ans;
        assert(mid>=1);
        for(int i = 0;i<=n;i++){
            if(x>solve(arr[i+1]-arr[i]-1)){
                x-=solve(arr[i+1]-arr[i]-1);
                for(auto e:v)dp[e] = -1;
                v.clear();
            }else{
                assert(x>=1);assert(mid>=1);
                cout<<ge(arr[i]+1,arr[i+1]-1,-1,-1,x)<<endl;
                goto z;
            }
        }
        assert(0);
    }
    return 0;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59