제출 #762979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762979		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++11	100 / 100	152 ms	16948 KiB

ho_t1

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const int LIM=2e5;
const int INF = 1e18;
const string name="neckties";
int n,m;
int b[LIM+5];
int ans[LIM+5];
vector<pii> a;
	int st1[4*LIM+5];
	int st2[4*LIM+5];
	int bound;
	int merge(int a,int b){
		//CODE MERGE
		return max(a,b);
	}
	void build1(int id,int ss,int se){
	     //BUID INITTIALLY TREE
	     if(ss==se){
	     	st1[id]=max(0ll,a[ss].f - b[ss-1]);
	     	return;
		 }
		 int mid=(ss+se)>>1;
		 build1(2*id+1,ss,mid);
		 build1(2*id+2,mid+1,se);
		 st1[id]=merge(st1[2*id+1],st1[2*id+2]);
	}

	int _query1(int id,int ss,int se,int qs,int qe){
	     //PROCESS
	     if(ss>qe || se<qs){
		 	return -INF;
		 }
		 if(qs<=ss && qe>=se){
		    // UPDATE NODE;
		    return st1[id];
		 }
		int mid=(ss+se)>>1;
		int left_child=_query1(2*id+1,ss,mid,qs,qe);
	    int right_child=_query1(2*id+2,mid+1,se,qs,qe);
	    return merge(left_child,right_child);
	}
     int query1(int qs,int qe){
	 return _query1(0,1,bound,qs,qe);
	}
     void build2(int id,int ss,int se){
	     //BUID INITTIALLY TREE
	     if(ss==se){
	     	st2[id]=max(0ll,a[ss].f - b[ss]);
	     	return;
		 }
		 int mid=(ss+se)>>1;
		 build2(2*id+1,ss,mid);
		 build2(2*id+2,mid+1,se);
		 st2[id]=merge(st2[2*id+1],st2[2*id+2]);
	}
	int _query2(int id,int ss,int se,int qs,int qe){
	     //PROCESS
	     if(ss>qe || se<qs){
		 	return -INF;
		 }
		 if(qs<=ss && qe>=se){
		    // UPDATE NODE;
		    return st2[id];
		 }
		int mid=(ss+se)>>1;
	    int left_child=_query2(2*id+1,ss,mid,qs,qe);
	    int right_child=_query2(2*id+2,mid+1,se,qs,qe);
	    return merge(left_child,right_child);
	}
     int query2(int qs,int qe){
	 return _query2(0,0,bound-1,qs,qe);
	}
void solve(){
	//CODE GOES HERE
	cin>>n;
	for(int i=0;i<=n;++i){
		int x;
		cin>>x;
		a.push_back({x,i});
	}
	for(int i=0;i<n;++i){
		cin>>b[i];
	}
	sort(a.begin(),a.end());
	sort(b,b+n);
	build1(0,1,n);
	build2(0,0,n-1);
    bound = n;
	vector<int> v;
//	cout<<query2(0ll,0ll)<<endl;
	for(int i=0;i<=n;++i){
		if(i==0){
			ans[a[i].s] = st1[0];
		}
		else if(i<n){
			ans[a[i].s] = max(query2(0,i-1),query1(i+1,n));
		}
		else{
			ans[a[i].s]=query2(0ll,n-1);
		}
	}
	for(int i=0;i<=n;++i){
		cout<<ans[i]<<" ";
	}
}
signed main(){
//   freopen((name+".inp").c_str(),"r",stdin);
//   freopen((name+".out").c_str(),"w",stdout);
  //  ifstream cin(".txt");
  //  ofstream cout(".txt");
    //ifstream cin((name +".inp"));
    //ofstream cout((name +".ans"));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91