oj.uz

Submission #788731

# Submission time Handle Problem Language Result Execution time Memory
788731 2023-07-20T14:34:19 Z Ahmed57 OGLEDALA (COI15_ogledala) C++17
0 / 100
 4000 ms 6628 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
long long mid = 1;
unordered_map<long long,long long> dp;
long long lim = 1e18;
int a = 0;
long long solve(long long x){
    if(x<mid)return 0;
    if(dp.find(x)!=dp.end())return dp[x];
    a++;
    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;
    if(solve((len-1)/2)>=x){
        return ge(l,l+((len-1)/2)-1,l,r,x);
    }else{
        return ge(l+((len+1)/2),r,l,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;
    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);
            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;
        }
        assert(ans!=0);
        dp.clear();
        mid = ans+1;
        assert(mid>=1);
        for(int i = 0;i<=n;i++){
            x-=solve(arr[i+1]-arr[i]-1);
        }
        assert(x>=1);
        dp.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);
            }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.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 212 KB Output is correct
2 Correct 10 ms 212 KB Output is correct
3 Execution timed out 4088 ms 440 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 6628 KB Time limit exceeded
2 Halted 0 ms 0 KB -