oj.uz

Submission #618989

# Submission time Handle Problem Language Result Execution time Memory
618989 2022-08-02T08:47:06 Z sentheta OGLEDALA (COI15_ogledala) C++17
41 / 100
 344 ms 44760 KB 
#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define all(x) (x).begin(), (x).end()

#define int long long
const int N = 3e5+5;

int m, n, q;

// {len, -l, r}
set<array<int,3>> s;
void insert(int l,int r){
	s.insert({r-l+1, -l, r});
}

int ans[N];

signed main(){

	cin >> m >> n >> q;

	V<int> taken;
	rep(i,1,n+1){
		int x;
		cin >> x;

		ans[i] = x;
		taken.push_back(x);
	}
	
	sort(all(taken));
	if(1<taken[0]){
		insert(1,taken[0]-1);
	}
	if(taken.back()<m){
		insert(taken.back()+1,m);
	}
	rep(i,0,n-1){
		insert(taken[i]+1,taken[i+1]-1);
	}


	rep(i,n+1,min(N,m+1)){
		auto[len,l,r] = *prev(s.end());
		l *= -1;
		s.erase(prev(s.end()));

		int mid;
		if(len&1) mid = l+len/2;
		else mid = l+len/2-1;

		ans[i] = mid;

		if(l<mid) insert(l,mid-1);
		if(mid<r) insert(mid+1,r);
	}

	while(q--){
		int i;
		cin >> i;

		cout << ans[i] << nl;
	}

	
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 162 ms 4176 KB Output is correct
4 Correct 159 ms 4212 KB Output is correct
5 Correct 278 ms 13204 KB Output is correct
6 Correct 238 ms 12396 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 21432 KB Output is correct
2 Correct 108 ms 21460 KB Output is correct
3 Correct 344 ms 23480 KB Output is correct
4 Correct 309 ms 23628 KB Output is correct
5 Correct 328 ms 23684 KB Output is correct
6 Correct 344 ms 23720 KB Output is correct

Subtask #3
0 / 59.0

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