Submission #1159878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159878		gigo_g	OGLEDALA (COI15_ogledala)	C++17	19 / 100	124 ms	6224 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 long long ll;

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

int main(){
    cin >> m >> n >> q;
    a.resize(m+1);
    ll prev = 0;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] > prev+1){
            pair<ll, pair<ll, ll>> np = {a[i]-prev-1, {-(prev+1), a[i]-1}};
            pq.push(np);
//            cout << "llerval [" << np.second.first << ", " << np.second.second << "] (" << np.first << ")\n";
        }
        prev = a[i];
    }
    if(prev < m){
        pair<ll, pair<ll, ll>> np = {m-prev, {-(prev+1), m}};
        pq.push(np);
//        cout << "lastllv [" << np.second.first << ", " << np.second.second << "] (" << np.first << ")\n";
    }
    /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// /// ///
    for(ll i = n+1; i <= m; i++){
        pair<ll, pair<ll, ll>> p = pq.top(); pq.pop();
        p.second.first *= -1;
//        cerr << '[' << p.second.first << ", " << p.second.second << "] (" << p.first << ")\n";
        ll mid = (p.second.first + p.second.second)/2;
        if(mid > p.second.first){
            pair<ll, pair<ll, ll>> 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<ll, pair<ll, ll>> 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(ll i = 0; i < q; i++){
        ll b;
        cin >> b;
        cout << a[b] << '\n';
    }

    return 0;
}

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