Submission #274176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274176	2020-08-19T09:27:14 Z	theStaticMind	Santa Claus (RMI19_santa)	C++14	100 / 100	514 ms	9780 KB

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;

int S;

struct MinSeg{
	vector<int> seg;
	vector<int> lazy;
	MinSeg(int size);
	void build();
	void push(int j);
	void pull(int j);
	void rangeupdate(int j, int x, int y, int l, int r, int v);
	int rangequery(int j, int x, int y, int l, int r);
};


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];

		map<int, int> compress;
		compress[0] = 0;
		for(auto x : V) compress[x] = 0;
		int ind = 0;
		for(auto& x : compress){
			x.second = ind++;
		} 

		multiset<int> elf;
		vector<int> edge(n, -1);

		int last = 0;
		for(int i = 0; i < n; i++){
			if(!H[i]){
				last = i;
				elf.insert(V[i]);
			}
			else{
				auto itr = elf.lower_bound(V[i]);
				if(itr != elf.end()){
					edge[i] = *itr;
					elf.erase(itr);
				}

			}
		}

		vector<int> ans(n);
		for(int i = 0; i < last; i++){
			ans[i] = -1;
		}
		
		MinSeg pref(sz(compress));

		for(auto x : elf){
			pref.rangeupdate(1, 0, S - 1, compress[x], S - 1, -1);
		}

		int ptr = n - 1;
		for(int i = n - 1; i >= last; i--){
			while(ptr >= i || (pref.rangequery(1, 0, S - 1, 0, S - 1) < 0 && ptr >= 0)){
				if(edge[ptr] >= 0){
					pref.rangeupdate(1, 0, S - 1, compress[edge[ptr]], S - 1, -1);
				}
				if(H[ptr]) pref.rangeupdate(1, 0, S - 1, compress[V[ptr]], S - 1, 1);

				ptr--;
			}

			if((pref.rangequery(1, 0, S - 1, 0, S - 1) < 0)) ans[i] = -1;
			else ans[i] = 2 * X[i] - X[ptr + 1];

			pref.rangeupdate(1, 0, S - 1, compress[V[i]], S - 1, -1);

		}
		for(int i = 0; i < n; i++) cout << ans[i] << " ";
		cout << "\n";
	}
	
}

MinSeg::MinSeg(int N){
	seg = vector<int> (N, 0);
	build();
}

void MinSeg::build(){
	S = 1 << (int)(ceil(log2(sz(seg))));
	while(sz(seg) != S) seg.pb(0);

	reverse(all(seg));
	for(int i = 1; i < sz(seg); i += 2){
		seg.pb(min(seg[i - 1], seg[i]));
	}
	seg.pb(0);
	reverse(all(seg));

	lazy = vector<int>(sz(seg), 0);
}

void MinSeg::push(int j){
	if(0 < j && j < sz(seg)){
		seg[j] += lazy[j];

		if(j * 2 < sz(seg)){
			lazy[j * 2] += lazy[j];
			lazy[j * 2 + 1] += lazy[j];
		}

		lazy[j] = 0;
	}
}

void MinSeg::pull(int j){
	push(j);
	if(j * 2 < sz(seg)){
		push(j * 2);
		push(j * 2 + 1);
		seg[j] = min(seg[j * 2], seg[j * 2 + 1]);
	}
}

void MinSeg::rangeupdate(int j, int x, int y, int l, int r, int v){
	if(y < l || r < x) return;
	push(j);
	if(l <= x && y <= r){
		lazy[j] += v;
	}
	else{
		rangeupdate(j*2,x,(x+y)/2,l,r,v);
		rangeupdate(j*2+1,(x+y)/2+1,y,l,r,v);
	}
	pull(j);
}

int MinSeg::rangequery(int j, int x, int y, int l, int r){
	if(y < l || r < x) return 1e9;
	push(j);
	if(l <= x && y <= r){
		return seg[j];
	}
	else{
		return min(
			rangequery(j*2,x,(x+y)/2,l,r),
			rangequery(j*2+1,(x+y)/2+1,y,l,r)
			);
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	12 ms	512 KB	Output is correct
4	Correct	22 ms	896 KB	Output is correct
5	Correct	59 ms	1548 KB	Output is correct
6	Correct	89 ms	2116 KB	Output is correct
7	Correct	188 ms	3652 KB	Output is correct
8	Correct	274 ms	5480 KB	Output is correct
9	Correct	350 ms	6780 KB	Output is correct
10	Correct	514 ms	9780 KB	Output is correct