Submission #329310

#	Time	Username	Problem	Language	Result	Execution time	Memory
329310		seastar105	OGLEDALA (COI15_ogledala)	C++14	41 / 100	4070 ms	201612 KiB

ogledala

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll len, cnt, idx;
    bool operator< (const Node &rhs) {
        if(len == rhs.len) return idx < rhs.idx;
        return len > rhs.len;
    }
};

ll N, M, Q;
ll A[100005];
ll B[100005];
ll ans[100005];
map<ll,ll> mp;
vector<pair<ll,ll>> ret;

void calc_seg(ll len) {
    ret.clear();
    mp.clear();
    mp[len] = 1;
    while(!mp.empty()) {
        assert(mp.size() <= 100);
        auto it = prev(mp.end());
        ll l = it->first;
        ll cnt = it->second;
        if(l == 0) break;
        ret.push_back({l,cnt});
        if(l>1) {
            if(l%2) mp[l/2] += cnt*2;
            else {
                mp[l/2] += cnt;
                if(l/2 != 1) mp[l/2-1] += cnt;
            }
        }
        mp.erase(it);
    }
    return ;
}

ll calc_pos(int idx, ll tar_len, ll K) {
    ll len = A[idx+1] - A[idx] - 1;
    ll pos = A[idx];
    while(len > tar_len) {  // O(logM)
        calc_seg((len-1) / 2); // O(logM)
        ll cnt = 0;
        for(const auto &p:ret) if(tar_len == p.first) cnt += p.second;
        if(cnt >= K) len = (len-1) / 2;
        else {
            pos += (len-1)/2 + 1;
            len >>= 1;
            K -= cnt;
        }
    }
    return pos + (len+1)/2;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> M >> N >> Q;
    for(int i=1;i<=N;++i) cin >> A[i];
    A[0] = 0; A[N+1] = M+1;
    for(int i=1;i<=Q;++i) cin >> B[i];
    vector<Node> segment;
    for(int i=0;i<=N;++i) {
        ll len = A[i+1] - A[i] - 1;
        if(len>0) {
            calc_seg(len);
            for(const auto &p:ret) segment.push_back({p.first, p.second, i});
        }
    }   // O(NlogM)
    sort(segment.begin(), segment.end()); // O(NlogM * (logN + log(logM))
    int q = 1;
    while(q <= Q && B[q] <= N) {
        ans[q] = A[B[q]];
        ++q;
    }
    ll pos = N;
    for(const auto &seg:segment) {  // O(NlogM)
        while(q<=Q && B[q] <= pos+seg.cnt) {
            ans[q] = calc_pos(seg.idx, seg.len, B[q]-pos);  // O(log^2M)
            ++q;
        }
        pos += seg.cnt;
    }
    for(int q=1;q<=Q;++q) cout << ans[q] << '\n';
    return 0;
}

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