답안 #259659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259659	2020-08-08T07:25:01 Z	oolimry	Santa Claus (RMI19_santa)	C++14	0 / 100	17 ms	6912 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(){
	freopen("i.txt","r",stdin);
	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;
		}
		
		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 << 2*X[i] - X[ans[i]] << " ";
			}
		}
		cout << "\n";
	}
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:63:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("i.txt","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	11 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	11 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	12 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	12 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	17 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	13 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	11 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	10 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	10 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)