Submission #846448

#	Time	Username	Problem	Language	Result	Execution time	Memory
846448		vjudge1	OGLEDALA (COI15_ogledala)	C++11	41 / 100	102 ms	18108 KiB

ogledala

#include <bits/stdc++.h>
#define lg(a) (31 - __builtin_clz((a)))
#define endl ("\n")
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
#define rall(aa) aa.rbegin(), aa.rend()
#define until(n, v) (int) (lower_bound(v.begin(), v.end(), n)-v.begin()) //# of elements < n
#define after(n, v) (int) (v.end()-upper_bound(v.begin(), v.end(), n))   //# of elements > n
#define sameas(n, v) (int) (upper_bound(v.begin(), v.end(), n) - lower_bound(v.begin(), v.end(), n)) //# of elements ==n
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
/*

*/




void solve(){
	ll m; int n, qq; cin >> m >> n >> qq;

	vector<ll> initial(n);
	for(int i=0;i<n;i++){
		cin>>initial[i];
	}

	priority_queue<pair<ll, pair<ll, ll>>> q; // length, (l, r) range;
	for(int i=1;i<n;i++){
		q.push(mp(initial[i]-initial[i-1]-1, mp(-initial[i-1], -initial[i])));
	}
	q.push(mp(m-initial[n-1], mp(-initial[n-1], -m-1) ) );
	q.push(mp(initial[0]-1, mp(0, -initial[0])));
	vector<int> B(qq);
	for(int i=0;i<qq;i++){
		cin>>B[i];
		// cout<<B[i]<<endl;
	}

	vector<ll> ans(B[qq-1]+1);
	for(int i=0;i<n;i++){
		ans[i] = initial[i];
	}

	for(int i=n;i<=B[qq-1];i++){
		pair<ll, pair<ll, ll>> cur = q.top();
		ll dist = cur.st;
		ll l = -cur.nd.st;
		ll r = -cur.nd.nd;
		ll pos = (l+r)/2;
		// cout << dist<<' '<<l<<' '<<r<<' '<<pos<<endl;
		q.pop();
		q.push(mp(pos-l-1, mp(-l, -pos)));
		q.push(mp(r-pos-1, mp(-pos, -r)));
		ans[i] = pos;
	}
	// for(int i=0;i<=B[qq-1];i++){
	// 	cout<<ans[i]<<' ';
	// }
	for(int i=0;i<qq;i++){
		cout<<ans[B[i]-1]<<endl;
	}

}

int main(){
	int test; 
    // cin >> test;
    test =1;
   	while (test--){
		solve();
    }
}

Compilation message (stderr)

ogledala.cpp: In function 'void solve()':
ogledala.cpp:53:6: warning: unused variable 'dist' [-Wunused-variable]
   53 |   ll dist = cur.st;
      |      ^~~~

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