Submission #584497

#	Time	Username	Problem	Language	Result	Execution time	Memory
584497		FatihSolak	OGLEDALA (COI15_ogledala)	C++17	100 / 100	2992 ms	447076 KiB

ogledala

#include <bits/stdc++.h>
#define N 100005
#define K 105
using namespace std;
long long a[N],b[N];
long long len[N];
vector<pair<long long,long long>> get_proper(vector<pair<long long,long long>> a){
    vector<pair<long long,long long>> ret;
    for(int i = 0;i<a.size();i++){
        if(i + 1 != a.size() && a[i].first == a[i+1].first){
            a[i+1].second += a[i].second;
            continue;
        }
        ret.push_back(a[i]);
    }
    return ret;
}
pair<pair<long long,long long>,pair<long long,long long>> get(pair<pair<long long,long long>,pair<long long,long long>> nums){
    pair<pair<long long,long long>,pair<long long,long long>> nw = {{-1,-1},{-1,-1}};
    if(nums.second.first == -1){
        if(nums.first.first & 1){
            nw.first = {nums.first.first/2,2*nums.first.second};
        }
        else{
            nw.first = {nums.first.first/2,nums.first.second};
            nw.second = {nums.first.first/2 - 1,nums.first.second};
        }
    }
    else{
        if(nums.first.first & 1){
            nw.first = {nums.first.first/2,2*nums.first.second + nums.second.second};
            nw.second = {nums.first.first/2 - 1,nums.second.second};
        }
        else{
            nw.first = {nums.first.first/2,nums.first.second};
            nw.second = {nums.first.first/2 - 1,nums.first.second + 2*nums.second.second};
        }
    }
    return nw;
}
long long val(long long curlen,long long target){
    long long ret = 0;
    pair<pair<long long,long long>,pair<long long,long long>> nums = {{curlen,1},{-1,-1}};
    while(nums.first.first >= target){
        if(nums.first.first == target)ret += nums.first.second;
        if(nums.second.first == target)ret += nums.second.second;
        nums = get(nums);
    }
    return ret;
}
long long get(long long st,long long curlen,long long target,long long idx){
    if(curlen == target)return st + (target - 1)/2;
    long long nwlen = (curlen - 1)/2;
    long long x = val(nwlen,target);
    if(x >= idx){
        return get(st,nwlen,target,idx);
    }
    idx -= x;
    nwlen = (curlen)/2;
    return get(st + (curlen + 1)/2,nwlen,target,idx);
}
vector<pair<long long,long long>> mp[N * K]; 
void solve(){
    long long m,n,q;
    cin >> m >> n >> q;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    a[n+1] = m + 1;
    vector<long long> compress;
    for(int i = 0;i<=n;i++){
        len[i] = a[i+1] - a[i] - 1;
        pair<pair<long long,long long>,pair<long long,long long>> nums = {{len[i],1},{-1,-1}};
        while(nums.first.first >= 1){
            if(nums.first.first != -1)compress.push_back(nums.first.first);
            if(nums.second.first != -1)compress.push_back(nums.second.first);
            nums = get(nums);
        }
    }
    sort(compress.begin(),compress.end());
    compress.resize(unique(compress.begin(),compress.end()) - compress.begin());
    for(int i = 0;i<=n;i++){
        pair<pair<long long,long long>,pair<long long,long long>> nums = {{len[i],1},{-1,-1}};
        while(nums.first.first >= 1){
            if(nums.first.first != -1)mp[lower_bound(compress.begin(),compress.end(),nums.first.first) - compress.begin()].push_back({i,nums.first.second});
            if(nums.second.first != -1)mp[lower_bound(compress.begin(),compress.end(),nums.second.first) - compress.begin()].push_back({i,nums.second.second});
            nums = get(nums);
        }
    }
    for(int i = 0;i<compress.size();i++){
        mp[i] = get_proper(mp[i]);
        reverse(mp[i].begin(),mp[i].end());
    }
    int point = compress.size() -1;
    long long nowgo = n;
    for(int i = 1;i<=q;i++){
        cin >> b[i];
        if(b[i] <= n){
            cout << a[b[i]] << "\n";
            continue;
        }
        while(nowgo + mp[point].back().second < b[i]){
            nowgo += mp[point].back().second;
            mp[point].pop_back();
            if(mp[point].empty()){
                point--;
            }
        }   
        b[i] -= nowgo;
        cout << get( a[mp[point].back().first] + 1,len[mp[point].back().first],compress[point],b[i]) << "\n";
    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Compilation message (stderr)

ogledala.cpp: In function 'std::vector<std::pair<long long int, long long int> > get_proper(std::vector<std::pair<long long int, long long int> >)':
ogledala.cpp:9:20: 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]
    9 |     for(int i = 0;i<a.size();i++){
      |                   ~^~~~~~~~~
ogledala.cpp:10: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]
   10 |         if(i + 1 != a.size() && a[i].first == a[i+1].first){
      |            ~~~~~~^~~~~~~~~~~
ogledala.cpp: In function 'void solve()':
ogledala.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0;i<compress.size();i++){
      |                   ~^~~~~~~~~~~~~~~~

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