oj.uz

Submission #274311

# Submission time Handle Problem Language Result Execution time Memory
274311 2020-08-19T10:55:01 Z Fasho Santa Claus (RMI19_santa) C++14
20 / 100
 1000 ms 2680 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 57 ms 384 KB Output is correct
3 Execution timed out 1085 ms 504 KB Time limit exceeded
4 Execution timed out 1056 ms 736 KB Time limit exceeded
5 Execution timed out 1099 ms 560 KB Time limit exceeded
6 Execution timed out 1099 ms 736 KB Time limit exceeded
7 Execution timed out 1064 ms 1148 KB Time limit exceeded
8 Execution timed out 1100 ms 1400 KB Time limit exceeded
9 Execution timed out 1088 ms 2652 KB Time limit exceeded
10 Execution timed out 1086 ms 2680 KB Time limit exceeded