Submission #390679

#	Time	Username	Problem	Language	Result	Execution time	Memory
390679		PedroBigMan	Road Construction (JOI21_road_construction)	C++14	100 / 100	8406 ms	38252 KiB

road_construction

#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class FT
{
    public:
    int N;
    vector<int> a, f;
    FT(vector<int> z)
    {
        N = z.size(); a = z; int sum = 0;
        vector<int> ps; ps.pb(0); REP(i,0,N) {sum+=a[i]; ps.pb(sum);}
        REP(i,0,N+1)
        {
            f.pb(ps[i] - ps[i-(i&(-i))]);
        }
    }
    
    int sum(int s)
    {
        if(s<0) {return 0;}
        int cur = s+1; 
        int ans = 0;
        while(cur>0) 
        {
            ans+=f[cur];
            cur-=(cur&(-cur));
        }
        return ans;
    }
    
    void update(int s, int dif)
    {
        int cur = s+1;
        a[s]+=dif;
        while(cur<=N)
        {
            f[cur]+=dif;
            cur+=(cur&(-cur));
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cout.precision(20);
    ll N,K; cin>>N>>K;
	vector<pl> P; pl cur; REP(i,0,N) {cin>>cur.ff>>cur.ss; P.pb(mp(cur.ff+cur.ss,cur.ss-cur.ff));}
	sort(whole(P));
	vector<ll> Yvals; REP(i,0,N) {Yvals.pb(P[i].ss);}
	sort(whole(Yvals)); 
	unordered_map<ll,ll> comp; ll c=0LL; vector<ll> key;
	comp.reserve(1LL<<20LL); comp.max_load_factor(0.25);
	REP(i,0,Yvals.size()) 
	{
		if(i!=0 && Yvals[i]==Yvals[i-1]) {continue;}
		comp[Yvals[i]]=c; c++; key.pb(Yvals[i]);
	}
	ll lo = 1LL; ll hi = 5000000000LL; 
	vector<int> insig; REP(i,0,N) {insig.pb(0);}
	while(lo<hi)
	{
		FT S(insig);
		ll d=(lo+hi)/2LL;
		ll cnt=0LL;
		ll l=0LL; ll r=0LL; 
		S.update(comp[P[0].ss],1LL);
		REP(ind,0,N)
		{
			ll x = P[ind].ff; ll y = P[ind].ss; 
			while(l<N && P[l].ff<x-d) 
			{
				S.update(comp[P[l].ss],-1LL);
				l++;
			} 
			while(r<N && P[r].ff<=x+d) 
			{
				r++;
				if(r<N && P[r].ff<=x+d) {S.update(comp[P[r].ss],1LL);}
			} 
			r--;
			ll leftindex = (ll) (lower_bound(whole(key),y-d) - key.begin());
			ll rightindex = (ll) (upper_bound(whole(key),y+d) - key.begin()) -1LL;
			if(leftindex!=0) {cnt+=(S.sum(rightindex)-S.sum(leftindex-1LL));} 
			else {cnt+=S.sum(rightindex);} 
			cnt--;
		}
		cnt/=2LL;
		if(cnt>=K) {hi=d;}
		else {lo=d+1LL;}
	}
	ll d=lo-1LL;
	vector<ll> ans; 
	map<ll,deque<ll> > m; deque<ll> xxxx; 
	int l=0; int r=0LL; m[P[0].ss]=xxxx; m[P[0].ss].pb(P[0].ff);
	map<ll,deque<ll> >::iterator it; deque<ll>::iterator it2,it3;
	REP(ind,0,N)
	{
		ll x = P[ind].ff; ll y = P[ind].ss; 
		while(l<N && P[l].ff<x-d) 
		{
			m[P[l].ss].pop_front();
			if(m[P[l].ss].size()==0) {m.erase(P[l].ss);}
			l++;
		} 
		while(r<N && P[r].ff<=x+d) 
		{
			r++;
			if(r<N && P[r].ff<=x+d) {if(m.find(P[r].ss)==m.end()) {m[P[r].ss]=xxxx;} m[P[r].ss].pb(P[r].ff);}
		} 
		r--;
		it=m.lower_bound(y-d);
		while(it!=m.end() && it->ff<=y+d) 
		{
			it2=(it->ss).begin(); it3=(it->ss).end();
			ll dx,dy; dy = it->ff-y;
			while(it2!=it3)
			{
				ll dx = (*it2)-x; 
				ans.pb(max(abs(dx),abs(dy)));
				it2++;
			}
			it++;
		}
	}
	sort(whole(ans)); while(ans.size()!=2LL*K+N) {ans.pb(lo);}
	REP(i,0,ans.size()) 
	{
		if(ans[i]==0) {continue;}
		if(i%2==0) {cout<<ans[i]<<"\n";}
	}
    return 0;
}

Compilation message (stderr)

road_construction.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization ("O3")
      | 
road_construction.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      | 
road_construction.cpp: In function 'int main()':
road_construction.cpp:161:7: warning: unused variable 'dx' [-Wunused-variable]
  161 |    ll dx,dy; dy = it->ff-y;
      |       ^~
road_construction.cpp:171:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  171 |  sort(whole(ans)); while(ans.size()!=2LL*K+N) {ans.pb(lo);}
      |                          ~~~~~~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35