oj.uz

Submission #846442

# Submission time Handle Problem Language Result Execution time Memory
846442 2023-09-07T14:48:41 Z vjudge1 OGLEDALA (COI15_ogledala) C++11
19 / 100
 112 ms 16828 KB 
#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<int> 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

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

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 42 ms 4292 KB Output is correct
4 Correct 34 ms 4804 KB Output is correct
5 Correct 93 ms 16740 KB Output is correct
6 Correct 97 ms 16740 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14024 KB Output is correct
2 Correct 43 ms 14512 KB Output is correct
3 Incorrect 112 ms 16828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 7616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -