Submission #259671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259671	2020-08-08T07:36:13 Z	oolimry	Santa Claus (RMI19_santa)	C++14	100 / 100	515 ms	50336 KB

santa

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;
typedef long long lint;

struct node{
	
	int s, e, m;
	node *l, *r;
	int val = 0; int lazy = 0;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void apply(int L){
		val += L;
		lazy += L;
	}
	
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
	
	void update(int S, int E, int V){
		push();
		if(S == s && e == E){
			apply(V);
			return;
		}
		else if(E <= m) l->update(S,E,V);
		else if(S >= m+1) r->update(S,E,V);
		else{
			l->update(S,m,V); r->update(m+1,E,V);
		}
		val = min(l->val, r->val);
	}
	
	int query(int S, int E){
		push();
		if(S == s && e == E) return val;
		else if(E <= m) return l->query(S,E);
		else if(S >= m+1) return r->query(S,E);
		else{
			return min(l->query(S,m), r->query(m+1,E));
		}
	}
	
} *root;

const int give = 0, take = 1;

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int TC; cin >> TC;
	
	while(TC--){
		
		int n; cin >> n;
		int X[n], type[n], V[n];
		
		int lastGive = -1;
		for(int i = 0;i < n;i++) cin >> X[i];
		for(int i = 0;i < n;i++) cin >> type[i];
		for(int i = 0;i < n;i++) cin >> V[i];
		
		root = new node(1, n);
		
		for(int i = 0;i < n;i++){
			if(type[i] == give) lastGive = i;
		}
		
		if(lastGive == -1){
			for(int i = 0;i < n;i++) cout << X[i] << " ";
			cout << "\n";
			continue;
		}
		
		for(int i = 0;i <= lastGive;i++){
			if(type[i] == give) root->update(V[i], n, -1);
			else root->update(V[i], n, 1);
		}
		
		
		int ans[n]; fill(ans, ans+n, -1);
		int R = lastGive+1;
		multiset<int> beforeL;
		for(int L = 0;L < n;L++){
			
			while(R < n){
				//cout << L << " " << R-1 << ": " << root->query(1,n) << "F\n";
				if(root->query(1,n) >= 0) break;
				if(type[R] == give) root->update(V[R], n, -1);
				else root->update(V[R], n, 1);
				R++;
			}
			//cout << L << " " << R-1 << "\n";
			if(root->query(1,n) >= 0) ans[R-1] = L;
			
			///do the multiset thingy
			if(type[L] == give) beforeL.insert(V[L]);
			else{
				root->update(V[L], n, -1); ///undo previous add
				
				auto it = beforeL.lower_bound(V[L]);
				if(it == beforeL.end()) continue;
				
				//if(L == 2) cout << *it << " " << V[L] << "\n";
				
				root->update(*it, n, 1); ///if can find match
				beforeL.erase(it);
			}
		}
		
		for(int i = 0;i < n;i++){
			if(i != 0) ans[i] = max(ans[i], ans[i-1]);
			
			if(ans[i] == -1) cout << -1 << " ";
			else{
				cout << max(X[i],2*X[i] - X[ans[i]]) << " ";
				//cout << ans[i] << " ";
			}
		}
		cout << "\n";
	}
}

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	512 KB	Output is correct
3	Correct	10 ms	1664 KB	Output is correct
4	Correct	24 ms	3328 KB	Output is correct
5	Correct	54 ms	6648 KB	Output is correct
6	Correct	89 ms	10616 KB	Output is correct
7	Correct	172 ms	18552 KB	Output is correct
8	Correct	268 ms	28152 KB	Output is correct
9	Correct	349 ms	35448 KB	Output is correct
10	Correct	515 ms	50336 KB	Output is correct