Submission #274311

#	Time	Username	Problem	Language	Result	Execution time	Memory
274311		Fasho	Santa Claus (RMI19_santa)	C++14	20 / 100	1100 ms	2680 KiB

santa

#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,val[N],b[N],tutmac;


bool check(int x,int y)
{
	multiset<int> st;
	multiset<int> ::iterator it;

	fo(i,1,x-1)
	{
		if(b[i]==0)
			st.insert(val[i]);
		else
		{
			it=st.lower_bound(val[i]);
			ll a=*it;
			if(a<val[i] || st.count(a)<=0)
				continue;
			st.erase(it);
		}
	}

	fo(i,x,y)
	{
		if(b[i]==0)
			st.insert(val[i]);
	}

	// cout<<endl;
	// if(y==6 &&x==1)
	// 	cout<<"[d2]"<<endl;
	fo(i,x,y)
	{
		if(b[i]==1)
		{
			// if(y==6 &&x==1)
			// 	cout<<"[dd]"<<sp<<st.count(3)<<endl;
			it=st.lower_bound(val[i]);
			ll a=*it;
			if(a<val[i] || st.count(a)<=0)
				continue;
			// if(y==6 &&x==1)
			// 	cout<<a<<sp;
			st.erase(it);
		}
	}
	// if(y==6 && x==1)
	// 	cout<<"[ddd]"<<sp<<st.count(3)<<endl;
	// if(y==6 && x==1)
	// if(y==8)
	// {
	// 	cout<<endl;
	// 	cout<<"[d]"<<sp;
	// 	cout<<x<<sp<<st.size()<<endl;
	// }
	// cout<<endl<<"[d]"<<sp;
	// if(y==6 && x==1)
	// 	cout<<st.size()<<sp<<x<<endl;
	if(st.size() || tutmac>y)
		return 0;
	return 1;
}


ll bs(int l,int r,int x)
{
	while(l<r)
	{
		if(l==r-1)
		{
			if(check(r,x))
				l=r;
			break;
		}
		int mid=(l+r)/2;
		// if(x==8)
		// 	cout<<"[d3]"<<sp<<mid<<endl;
		if(check(mid,x))
			l=mid;
		else
			r=mid-1;
	}
	if(!check(l,x))
		return -1;
	return l;

}
int main()
{
	fast;
	cin>>t;
	while(t--)
	{
		cin>>n;
		fs(ar,n);
		fs(b,n);
		fs(val,n);
		fo(i,1,n)
		if(b[i]==0)
			tutmac=i;
		fo(i,1,n)
		{
			ll x=bs(1,i,i);
			if(x==-1)
			{
				cout<<-1<<sp;
				continue;
			}
			cout<<ar[i]*2-ar[x]<<sp;
		}
		cout<<endl;
		


	}


} 

• Subtask 1: 20 / 100