oj.uz

답안 #273939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
273939 2020-08-19T07:55:58 Z theStaticMind Santa Claus (RMI19_santa) C++14
20 / 100
 1000 ms 5368 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

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

		vector<int> X(n), H(n), V(n);

		for(int i = 0; i < n; i++) cin >> X[i];
		for(int i = 0; i < n; i++) cin >> H[i];
		for(int i = 0; i < n; i++) cin >> V[i];


		multiset<int> elf;
		int last = 0;
		for(int i = 0; i < n; i++){
			if(!H[i]){
				last = i;
				elf.insert(V[i]);
			}
		}

		for(int i = 0; i < last; i++){
			cout << -1 << " ";
		}
		for(int i = last; i < n; i++){

			int l = 0, r = i, xleft = -1;

			while(l <= r){
				int m = (l + r) / 2;

				multiset<int> elves;

				for(int j = 0; j < m; j++){
					if(H[j]){
						auto itr = elves.lower_bound(V[j]);
						if(itr != elves.end()) elves.erase(itr);
					}
					else elves.insert(V[j]);
				}
				for(int j = m; j <= i; j++){
					if(!H[j]) elves.insert(V[j]);
				}
				for(int j = m; j <= i; j++){
					if(H[j]){
						auto itr = elves.lower_bound(V[j]);
						if(itr != elves.end()) elves.erase(itr);
					}
				}
				if(elves.empty()){
					l = m + 1;
					xleft = m;
				}
				else{
					r = m - 1;
				}
			}

			if(xleft == -1) cout << -1 << " ";
			else cout << 2 * X[i] - X[xleft] << " ";
		}
		cout << "\n";
	}
	
}

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 17 ms 384 KB Output is correct
3 Execution timed out 1052 ms 384 KB Time limit exceeded
4 Execution timed out 1062 ms 512 KB Time limit exceeded
5 Execution timed out 1067 ms 640 KB Time limit exceeded
6 Execution timed out 1075 ms 896 KB Time limit exceeded
7 Execution timed out 1097 ms 1792 KB Time limit exceeded
8 Execution timed out 1079 ms 2432 KB Time limit exceeded
9 Execution timed out 1084 ms 5088 KB Time limit exceeded
10 Execution timed out 1075 ms 5368 KB Time limit exceeded