oj.uz

Submission #329310

# Submission time Handle Problem Language Result Execution time Memory
329310 2020-11-20T12:58:52 Z seastar105 OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 201612 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 53 ms 3684 KB Output is correct
4 Correct 43 ms 3808 KB Output is correct
5 Correct 65 ms 9564 KB Output is correct
6 Correct 66 ms 9564 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 832 KB Output is correct
2 Correct 103 ms 812 KB Output is correct
3 Correct 1407 ms 201088 KB Output is correct
4 Correct 1331 ms 201124 KB Output is correct
5 Correct 1582 ms 201264 KB Output is correct
6 Correct 1487 ms 201228 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2183 ms 102644 KB Output is correct
2 Correct 2119 ms 102644 KB Output is correct
3 Execution timed out 4070 ms 201612 KB Time limit exceeded
4 Halted 0 ms 0 KB -