Submission #1159848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159848		gigo_g	OGLEDALA (COI15_ogledala)	C++17	0 / 100	2 ms	328 KiB

ogledala

/**
  * @name Ogledala
  * @link https://oj.uz/problem/view/COI15_ogledala
  * @file ogledala
  * @from CROATIAN OLYMPIAD IN INFORMATICS 2015
  * @solutionBy Gigo_G
  */

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull m, n, q;
vector<ull> a;
priority_queue<pair<ull, pair<ull, ull>>> pq;

int main(){
    cin >> m >> n >> q;
    a.resize(m+1);
    ull prev = 0;
    for(ull i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] > prev+1){
            pq.push({a[i]-prev-1, {-(prev+1), a[i]-1}});
            prev = a[i];
        }
    }
    if(prev < m){
        pq.push({m-prev, {-(prev+1), m}});
    }

    for(ull i = n+1; i <= m; i++){
        pair<ull, pair<ull, ull>> p = pq.top(); pq.pop();
        p.second.first *= -1;
//        cerr << '[' << p.second.first << ", " << p.second.second << "] (" << p.first << ")\n";
        ull mid = (p.second.first + p.second.second)/2;
        if(mid > p.second.first){
            pair<ull, pair<ull, ull>> np = {mid-p.second.first, {-(p.second.first), mid-1}};
            pq.push(np);
//            cerr << "\tadd [" << np.second.first << ", " << np.second.second << "] (" << np.first << ")\n";
        }
        if(mid < p.second.second){
            pair<ull, pair<ull, ull>> np = {p.second.second-mid, {-(mid+1), p.second.second}};
            pq.push(np);
//            cerr << "\tadd [" << np.second.first << ", " << np.second.second << "] (" << np.first << ")\n";
        }
//        cerr << "\ta[" << i << "] = " << mid << '\n';
        a[i] = mid;
    }

    for(ull i = 0; i < q; i++){
        ull b;
        cin >> b;
        cout << a[b] << '\n';
    }

    return 0;
}

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