Submission #584473

#TimeUsernameProblemLanguageResultExecution timeMemory
584473FatihSolakOGLEDALA (COI15_ogledala)C++17
19 / 100
4108 ms462424 KiB
#include <bits/stdc++.h> #define N 100005 #define K 105 using namespace std; long long a[N],b[N]; long long len[N]; map<pair<long long,long long>,long long> rem; long long val(long long curlen,long long target){ if(curlen <= target)return curlen == target; if(rem.count({curlen,target})) return rem[{curlen,target}]; return rem[{curlen,target}] = val((curlen-1)/2,target) + val(curlen/2,target); } 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; if(val(nwlen,target) >= idx){ return get(st,nwlen,target,idx); } idx -= val(nwlen,target); nwlen = (curlen)/2; return get(st + (curlen + 1)/2,nwlen,target,idx); } vector<pair<long long,long long>> get_proper(vector<pair<long long,long long>> a){ vector<pair<long long,long long>> ret; if(!is_sorted(a.begin(),a.end())) sort(a.begin(),a.end()); 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; } 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; vector<pair<long long,long long>> nums = {{len[i],1}}; while(nums.back().first > 0){ vector<pair<long long,long long>> nw; for(auto u:nums){ compress.push_back({u.first}); nw.push_back({(u.first-1)/2,u.second}); nw.push_back({u.first/2,u.second}); } nums = get_proper(nw); } } sort(compress.begin(),compress.end()); compress.resize(unique(compress.begin(),compress.end()) - compress.begin()); for(int i = 0;i<=n;i++){ vector<pair<long long,long long>> nums = {{len[i],1}}; while(nums.back().first > 0){ vector<pair<long long,long long>> nw; for(auto u:nums){ mp[lower_bound(compress.begin(),compress.end(),u.first) - compress.begin()].push_back({i,u.second}); nw.push_back({(u.first-1)/2,u.second}); nw.push_back({u.first/2,u.second}); } nums = get_proper(nw); } } 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:29: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]
   29 |     for(int i = 0;i<a.size();i++){
      |                   ~^~~~~~~~~
ogledala.cpp:30: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]
   30 |         if(i + 1 != a.size() && a[i].first == a[i+1].first){
      |            ~~~~~~^~~~~~~~~~~
ogledala.cpp: In function 'void solve()':
ogledala.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0;i<compress.size();i++){
      |                   ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...