oj.uz

Submission #584454

# Submission time Handle Problem Language Result Execution time Memory
584454 2022-06-27T12:04:48 Z FatihSolak OGLEDALA (COI15_ogledala) C++17
19 / 100
 4000 ms 309516 KB 
#include <bits/stdc++.h>
#define N 100005
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;
    //cout << st << " " << curlen << " " << target << " " << idx << endl;
    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);
}
void solve(){
    long long m,n,q;
    cin >> m >> n >> q;
    map<long long,vector<pair<long long,long long>>> mp; 
    set<long long> points;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    a[n+1] = m + 1;
    for(int i = 0;i<=n;i++){
        len[i] = a[i+1] - a[i] - 1;
        map<long long,long long> cnt;
        cnt[len[i]] = 1;
        set<long long> nums = {len[i]};
        while(*nums.rbegin() > 0){
            long long nowlen = *nums.rbegin();
            nums.erase(nowlen);
            points.insert(nowlen);
            mp[nowlen].push_back({i,cnt[nowlen]});
            nums.insert((nowlen-1)/2);
            nums.insert(nowlen/2);
            cnt[(nowlen-1)/2] += cnt[nowlen];
            cnt[nowlen/2] += cnt[nowlen];
        }
    }
    for(auto &u:mp){
        reverse(u.second.begin(),u.second.end());
    }
    if(m > 1e10)return;
    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[*points.rbegin()].back().second < b[i]){
            nowgo += mp[*points.rbegin()].back().second;
            mp[*points.rbegin()].pop_back();
            if(mp[*points.rbegin()].empty()){
                points.erase(*points.rbegin());
            }
        }   
        b[i] -= nowgo;
        cout << get( a[mp[*points.rbegin()].back().first] + 1,len[mp[*points.rbegin()].back().first],*points.rbegin(),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
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 33 ms 2324 KB Output is correct
4 Correct 31 ms 2508 KB Output is correct
5 Correct 74 ms 6072 KB Output is correct
6 Correct 57 ms 7228 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1364 KB Output is correct
2 Correct 15 ms 1648 KB Output is correct
3 Execution timed out 4083 ms 309516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2686 ms 96920 KB Output is correct
2 Correct 2768 ms 97704 KB Output is correct
3 Incorrect 3877 ms 212116 KB Output isn't correct
4 Halted 0 ms 0 KB -