Submission #273939

#	Time	Username	Problem	Language	Result	Execution time	Memory
273939		theStaticMind	Santa Claus (RMI19_santa)	C++14	20 / 100	1097 ms	5368 KiB

santa

#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 / 100