Submission #788784

#	Time	Username	Problem	Language	Result	Execution time	Memory
788784		Ahmed57	OGLEDALA (COI15_ogledala)	C++17	0 / 100	3663 ms	524288 KiB

ogledala

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

using namespace std;
long long mid = 1;
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;
    vector<pair<long long,long long>> v[n+1];
    vector<pair<long long,long long>> all;
    map<long long,vector<pair<long long,long long>>> le;
    for(int i = 0;i<=n;i++){
        dp.clear();
        long long x = solve(arr[i+1]-arr[i]-1);
        vector<long long> elem;
        for(auto i:dp){
            elem.push_back(i.first);
        }
        //cout<<"hh"<<endl;
        v[i].push_back({elem[elem.size()-1],1});
        //cout<<elem.size()<<"sz"<<endl;
        //cout<<elem[elem.size()-1]<<"elem"<<endl;
        for(int j = elem.size()-2;j>=0;j--){
            //cout<<elem[j]<<"elem"<<endl;
            long long sum = 0;
            for(int e = 0;e<=2;e++){
                int ind = lower_bound(elem.begin(),elem.end(),elem[j]*2+e)-elem.begin();
                //cout<<ind<<"ind"<<endl;
                if(ind==elem.size())continue;
                if(elem[ind]!=elem[j]*2+e)continue;
                //cout<<ind<<"ind"<<endl;
                long long rev = elem.size()-1-ind;
                sum+=((e==1)+1)*v[i][rev].second;
                //cout<<"xd"<<endl;
            }
            v[i].push_back({elem[j],sum});
        }
        reverse(v[i].begin(),v[i].end());
        all.push_back(v[i][v[i].size()-1]);
        le[v[i][v[i].size()-1].first].push_back({v[i][v[i].size()-1].second,i});
        for(int j = v[i].size()-2;j>=0;j--){
            all.push_back(v[i][j]);
            le[v[i][j].first].push_back({v[i][j].second,i});
            v[i][j].second+=v[i][j+1].second;
        }
    }
    for(auto i:le){
        for(int j = 1;j<i.second.size();j++){
            le[i.first][j].first+=le[i.first][j-1].first;
        }
    }
    sort(all.begin(),all.end());
    for(int i = all.size()-2;i>=0;i--){
        all[i].second+=all[i+1].second;
    }
    while(q--){
        long long x;cin>>x;
        if(x<=n){
            cout<<arr[x]<<endl;
            continue;
        }
        x-=n;
        long long l=1,r=1e9 , ans = 0;
        while(l<=r){
            mid = (l+r)/2;
            int it = lower_bound(all.begin(),all.end(),make_pair(mid,0LL))-all.begin();
            long long al =0;
            if(it<all.size())al = all[it].second;
            if(al>=x){
                ans = mid;
                l = mid+1;
            }else r = mid-1;
        }
        //cout<<ans<<"anss"<<endl;
        int it = lower_bound(all.begin(),all.end(),make_pair(ans+1,0LL))-all.begin();
        long long al =0;
        if(it<all.size())al = all[it].second;
        x-=al;
        dp.clear();
        mid = ans;
        lim = ans;
        it = lower_bound(le[ans].begin(),le[ans].end(),make_pair(x,0LL))-le[ans].begin();
        if(it)x-=le[ans][it-1].first;
        it = le[ans][it].second;
        //cout<<arr[it]<<endl;
        dp.clear();
        cout<<ge(arr[it]+1,arr[it+1]-1,x)<<endl;
    }
    return 0;
}

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 if(ind==elem.size())continue;
      |                    ~~~^~~~~~~~~~~~~
ogledala.cpp:39:19: warning: unused variable 'x' [-Wunused-variable]
   39 |         long long x = solve(arr[i+1]-arr[i]-1);
      |                   ^
ogledala.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 1;j<i.second.size();j++){
      |                       ~^~~~~~~~~~~~~~~~
ogledala.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if(it<all.size())al = all[it].second;
      |                ~~^~~~~~~~~~~
ogledala.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(it<all.size())al = all[it].second;
      |            ~~^~~~~~~~~~~

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