Submission #781662

#	Time	Username	Problem	Language	Result	Execution time	Memory
781662		vjudge1	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	255 ms	31072 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define N 200005
map<pair<int,int>,int>mp;
int main(){
	lalala;
	int n;cin>>n;
	vector<pair<ll int,int>> arr;
	vector<ll int> mus;
	ll int cev[n+1];
	for(int i=0;i<n+1;i++){
		ll int a;cin>>a;
		arr.pb({a,i});
	}
	for(int i=0;i<n;i++){
		ll int a;cin>>a;
		mus.pb(a);
	}
	sort(arr.begin(),arr.end());sort(mus.begin(),mus.end());
	priority_queue<tuple<ll int ,int,int>> pq;
	for(int i=0;i<n;i++){
		if(mus[i]>arr[i+1].first){
			pq.push({(ll int)0,i,i+1});
		}
		else pq.push({arr[i+1].first-mus[i],i,i+1});
	}
	ll int a,b,c;
	tie(a,b,c)=pq.top();
	cev[arr[0].second]=a;
	for(int i=1;i<=n;i++){
		pq.push({max(arr[i-1].first-mus[i-1],(ll int)0),i-1,i-1});
		mp[{i-1,i}]=1;
		tie(a,b,c)=pq.top();
		while(mp[{b,c}]){
			pq.pop();
			tie(a,b,c)=pq.top();
		}
		cev[arr[i].second]=a;
	}
	for(int i=0;i<=n;i++)cout<<cev[i]<<" ";
	cout<<endl;

}

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