oj.uz

Submission #788702

# Submission time Handle Problem Language Result Execution time Memory
788702 2023-07-20T13:49:18 Z Ahmed57 OGLEDALA (COI15_ogledala) C++17
0 / 100
 4000 ms 8408 KB 
#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.count(x)!=0)return dp[x];
    return dp[x] =(x<=lim)+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);
    int m,n,q;
    cin>>m>>n>>q;
    int arr[n+2];
    arr[0] = 0;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    arr[n+1] = m+1;
    while(q--){
        int x;cin>>x;
        if(x<=n){
            cout<<arr[x]<<endl;
            continue;
        }
        x-=n;
        long long l=1,r=1e9 , ans = 0;
        lim = 1e18;
        while(l<=r){
            mid = (l+r)/2;
            dp.clear();
            int 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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 212 KB Output is correct
2 Correct 10 ms 212 KB Output is correct
3 Execution timed out 4073 ms 536 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 4051 ms 356 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 4070 ms 8408 KB Time limit exceeded
2 Halted 0 ms 0 KB -