oj.uz

Submission #846448

# Submission time Handle Problem Language Result Execution time Memory
846448 2023-09-07T14:53:01 Z vjudge1 OGLEDALA (COI15_ogledala) C++11
41 / 100
 102 ms 18108 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<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

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 348 KB Output is correct
3 Correct 36 ms 6080 KB Output is correct
4 Correct 34 ms 4812 KB Output is correct
5 Correct 85 ms 18108 KB Output is correct
6 Correct 82 ms 16828 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16832 KB Output is correct
2 Correct 43 ms 16064 KB Output is correct
3 Correct 97 ms 16828 KB Output is correct
4 Correct 96 ms 17228 KB Output is correct
5 Correct 101 ms 16568 KB Output is correct
6 Correct 102 ms 16928 KB Output is correct

Subtask #3
0 / 59.0

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