oj.uz

답안 #619292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619292 2022-08-02T10:59:07 Z MetalPower OGLEDALA (COI15_ogledala) C++14
0 / 100
 186 ms 57516 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 3e5 + 10;

#define ll long long

// Split segment based on A array (call them A segment), view them as if they are disjoint

// The only time where a segment affects another is only when finding which A segment a lady will go to

	// We will then split segments together in each A segment

	// Observe that there will be only O(logMAX) splits
	// And for each split there will only be at most 2 values, X and X+1

struct pli{
	ll fi, se;
	bool operator < (const pli& b) const{
		return fi < b.fi || (fi == b.fi && se > b.se);
	}
};

set<pli> s;

ll M; int N, Q;
ll arr[MX], ans[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> M >> N >> Q;
	for(int i = 0; i < N; i++) cin >> arr[i];

	s.insert({arr[0] - 1, 1});
	for(int i = 0; i < N - 1; i++) s.insert({arr[i + 1] - arr[i] - 1, arr[i] + 1});
	s.insert({M - arr[N - 1], arr[N - 1] + 1});

	int idx = 1;
	while(idx < MX && !s.empty()){
		set<pli>::iterator it = s.end(); it--;
		ll fv = ((*it).fi - 1) / 2, sv = ((*it).fi) / 2;
		ll stf = (*it).se, sts = (*it).se + fv + 1;
		ans[idx++] = stf + fv;
		s.erase(it);
		if(fv > 0) s.insert({fv, stf});
		if(sv > 0) s.insert({sv, sts});
	}

	for(int i = 0; i < Q; i++){
		ll x; cin >> x;
		cout << ans[x] << '\n';
	}
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 21436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 186 ms 57516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -