Submission #259670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259670	2020-08-08T07:35:22 Z	errorgorn	Santa Claus (RMI19_santa)	C++14	30 / 100	1000 ms	3320 KB

santa

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());


struct node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i){
		val++;
		
		if (s==e) return;
		else if (i<=m) l->update(i);
		else r->update(i);
	}
	
	void find(){
		val--;
		if (s==e) return;
		if (l->val!=0) l->find();
		else r->find();
	}
	
	bool query(int i){
		if (i<=s){
			if (val==0) return false;
			else{
				find();
				return true;
			}
		}
		if (i<=m){
			if (l->query(i) || r->query(i)){
				val--;
				return true;
			}
			else{
				return false;
			}
		}
		else{
			if (r->query(i)){
				val--;
				return true;
			}
			else{
				return false;
			}
		}
	}
	
	void clear(){
		val=0;
		if (s!=e){
			l->clear(),r->clear();
		}
	}
} *root=new node(0,3005);

int n;
int pos[100005];
int type[100005];
int val[100005];
int ans[100005];

bool test(int l,int r){
	root->clear();
	
	rep(x,0,r+1){
		if (x<l){
			if (type[x]==0){
				root->update(val[x]);
			}
		}
		else if (x==l){
			rep(x,l,r+1) if (type[x]==0){
				root->update(val[x]);
			}
		}
		
		if (type[x]==1){
			root->query(val[x]);
		}
	}
	
	return root->val==0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n) cin>>pos[x];
		rep(x,0,n) cin>>type[x];
		rep(x,0,n) cin>>val[x];
		
		bool bad=false;
		int curr=n-1;
		rep(x,n,0){
			if (bad) ans[x]=-1;
			else{
				while (curr>x || !test(curr,x)){
					curr--;
				}
				
				//cout<<x<<" "<<curr<<endl;
				if (curr==-1){
					bad=true;
					ans[x]=-1;
				}
				else{
					ans[x]=2*pos[x]-pos[curr];
				}
			}
			
			if (type[x]==0) bad=true;
		}
		
		rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
	}
}

Compilation message

santa.cpp: In constructor 'node::node(int, int)':
santa.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~
santa.cpp: In function 'int main()':
santa.cpp:19:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
                          ^
santa.cpp:165:3: note: in expansion of macro 'rep'
   rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
   ^~~
santa.cpp:165:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
                                 ^~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	640 KB	Output is correct
2	Correct	32 ms	640 KB	Output is correct
3	Correct	953 ms	716 KB	Output is correct
4	Execution timed out	1094 ms	760 KB	Time limit exceeded
5	Runtime error	3 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	5 ms	1408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	11 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	16 ms	2048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	43 ms	3320 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	34 ms	3320 KB	Execution killed with signal 11 (could be triggered by violating memory limits)