Submission #788705

#	Time	Username	Problem	Language	Result	Execution time	Memory
788705		Ahmed57	OGLEDALA (COI15_ogledala)	C++17	0 / 100	4041 ms	9148 KiB

ogledala

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
long long mid = 0;
map<long long,long long> dp;
long long lim = 1e18;
long long solve(long long x){
    if(x<mid)return 0;
    if(dp.find(x)!=dp.end())return dp[x];
    return dp[x]=(x<=lim?1LL:0LL)+solve(x/2)+solve((x-1)/2);
}
long long ge(long long l,long long r,long long x){
    if(x==1&&r-l+1==mid){
        return (l+r)/2;
    }
    long long len = r-l+1;
    if(solve((len-1)/2)>=x){
        return ge(l,l+((len-1)/2)-1,x);
    }else{
        return ge(l+((len+1)/2),r,x-solve((len-1)/2));
    }
}
signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    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;
    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;
            dp.clear();
            long long all = 0;
            for(int i = 0;i<=n;i++){
                all+=solve(arr[i+1]-arr[i]-1);
            }
            if(all>=x){
                ans = mid;
                l = mid+1;
            }else r = mid-1;
        }
        dp.clear();
        mid = ans+1;
        for(int i = 0;i<=n;i++){
            x-=solve(arr[i+1]-arr[i]-1);
        }
        dp.clear();
        mid = ans;
        lim = ans;
        for(int i = 0;i<=n;i++){
            if(x>solve(arr[i+1]-arr[i]-1)){
                x-=solve(arr[i+1]-arr[i]-1);
            }else{
                cout<<ge(arr[i]+1,arr[i+1]-1,x)<<endl;
                break;
            }
        }
    }
    return 0;
}

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