Submission #261027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261027	2020-08-11T10:05:45 Z	ryansee	Santa Claus (RMI19_santa)	C++14	100 / 100	649 ms	66552 KB

santa

#include "bits/stdc++.h"
using namespace std;

#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x,v) memset(x,v,sizeof(x))
#define siz(x) ll(x.size())
#define all(x) (x).begin(),(x).end()
#define lbd(x,y) (lower_bound(all(x),y)-(x).begin())
#define ubd(x,y) (upper_bound(all(x),y)-(x).begin())
mt19937 rng(123);
long long rand(long long x,long long y){return rng() % (y+1-x) + x; }
string to_string(char c){string s(1,c);return s;}

using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll t, n, A[MAXN], H[MAXN], V[MAXN];
struct node {
	int s,e,m;
	ll v,add;
	node*l,*r;
	node(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		v=add=0;
		if(s^e)l=new node(s,m),r=new node(m+1,e);
	}
	ll value(){
		v+=add;
		if(s^e){
			l->add+=add,r->add+=add;
		}
		add=0;
		return v;
	}
	void update(int x,int y,ll nval){
		if(s==x&&e==y) { add+=nval; return; }
		if(x>m) r->update(x,y,nval);
		else if(y<=m) l->update(x,y,nval);
		else l->update(x,m,nval), r->update(m+1,y,nval);
		v=min(l->value(),r->value());
	}
	ll rmq(int x,int y){
		value();
		if(s==x&&e==y) return v;
		if(x>m) return r->rmq(x,y);
		else if(y<=m) return l->rmq(x,y);
		else return min(l->rmq(x,m),r->rmq(m+1,y));
	}
} *seg;
int main(){
	FAST
	cin>>t;
	while(t--){
		cin>>n;
		seg=new node(0, n);
		FOR(i,1,n) cin>>A[i];
		FOR(i,1,n) cin>>H[i];
		FOR(i,1,n) cin>>V[i], assert(0<=V[i]&&V[i]<=n);
		ll elf = count(H+1, H+n+1, 0);
		if(elf == 0) {
			FOR(i,1,n) cout<<"0 "; 
			cout<<'\n';
			continue;
		}
		ll co = 1;
		multiset<ll> take;
		take.ins(-1);
		FOR(i,1,n){
			elf -= !H[i];
			if(H[i]){
				seg->update(V[i], n, 1);
			}else{
				seg->update(V[i], n, -1);
			}
			if(elf || seg->value() < 0) {
				cout<<"-1 ";
			}else{
				while(co < i){
					if(H[co]==0) { take.ins(V[co++]); continue; }
					auto gift=take.lower_bound(V[co]);
					if(gift!=take.end()) seg->update(*gift, n, 1);
					seg->update(V[co], n, -1);
					if(seg->value() < 0){
						seg->update(V[co], n, 1);
						if(gift!=take.end()) seg->update(*gift, n, -1);
						break;
					}
					++ co;
					if(gift!=take.end())take.erase(gift);
				}
				cout<<A[i]*2-A[co]<<' ';
			}
		}
		cout<<'\n';
		delete seg;
	}
}

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	12 ms	2176 KB	Output is correct
4	Correct	29 ms	4480 KB	Output is correct
5	Correct	65 ms	8824 KB	Output is correct
6	Correct	110 ms	14072 KB	Output is correct
7	Correct	205 ms	24440 KB	Output is correct
8	Correct	379 ms	37240 KB	Output is correct
9	Correct	442 ms	47204 KB	Output is correct
10	Correct	649 ms	66552 KB	Output is correct