Submission #390678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390678	2021-04-16T13:43:28 Z	PedroBigMan	Road Construction (JOI21_road_construction)	C++14	100 / 100	9297 ms	42476 KB

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<<19LL); 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

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	11948 KB	Output is correct
2	Correct	99 ms	12032 KB	Output is correct
3	Correct	92 ms	11952 KB	Output is correct
4	Correct	86 ms	12048 KB	Output is correct
5	Correct	86 ms	10788 KB	Output is correct
6	Correct	9 ms	4812 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3520 ms	41700 KB	Output is correct
2	Correct	3627 ms	41816 KB	Output is correct
3	Correct	79 ms	11892 KB	Output is correct
4	Correct	3298 ms	41480 KB	Output is correct
5	Correct	3135 ms	41852 KB	Output is correct
6	Correct	2944 ms	41824 KB	Output is correct
7	Correct	2366 ms	40972 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7437 ms	30944 KB	Output is correct
2	Correct	7729 ms	30940 KB	Output is correct
3	Correct	7 ms	4684 KB	Output is correct
4	Correct	3140 ms	30952 KB	Output is correct
5	Correct	1888 ms	16712 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7437 ms	30944 KB	Output is correct
2	Correct	7729 ms	30940 KB	Output is correct
3	Correct	7 ms	4684 KB	Output is correct
4	Correct	3140 ms	30952 KB	Output is correct
5	Correct	1888 ms	16712 KB	Output is correct
6	Correct	7810 ms	30940 KB	Output is correct
7	Correct	7949 ms	30940 KB	Output is correct
8	Correct	3 ms	4684 KB	Output is correct
9	Correct	3 ms	4668 KB	Output is correct
10	Correct	7746 ms	30180 KB	Output is correct
11	Correct	2663 ms	30948 KB	Output is correct
12	Correct	1847 ms	16696 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	11948 KB	Output is correct
2	Correct	99 ms	12032 KB	Output is correct
3	Correct	92 ms	11952 KB	Output is correct
4	Correct	86 ms	12048 KB	Output is correct
5	Correct	86 ms	10788 KB	Output is correct
6	Correct	9 ms	4812 KB	Output is correct
7	Correct	2620 ms	21920 KB	Output is correct
8	Correct	2771 ms	21920 KB	Output is correct
9	Correct	88 ms	11944 KB	Output is correct
10	Correct	2213 ms	21512 KB	Output is correct
11	Correct	2025 ms	21176 KB	Output is correct
12	Correct	668 ms	18316 KB	Output is correct
13	Correct	769 ms	18296 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	11948 KB	Output is correct
2	Correct	99 ms	12032 KB	Output is correct
3	Correct	92 ms	11952 KB	Output is correct
4	Correct	86 ms	12048 KB	Output is correct
5	Correct	86 ms	10788 KB	Output is correct
6	Correct	9 ms	4812 KB	Output is correct
7	Correct	3520 ms	41700 KB	Output is correct
8	Correct	3627 ms	41816 KB	Output is correct
9	Correct	79 ms	11892 KB	Output is correct
10	Correct	3298 ms	41480 KB	Output is correct
11	Correct	3135 ms	41852 KB	Output is correct
12	Correct	2944 ms	41824 KB	Output is correct
13	Correct	2366 ms	40972 KB	Output is correct
14	Correct	7437 ms	30944 KB	Output is correct
15	Correct	7729 ms	30940 KB	Output is correct
16	Correct	7 ms	4684 KB	Output is correct
17	Correct	3140 ms	30952 KB	Output is correct
18	Correct	1888 ms	16712 KB	Output is correct
19	Correct	7810 ms	30940 KB	Output is correct
20	Correct	7949 ms	30940 KB	Output is correct
21	Correct	3 ms	4684 KB	Output is correct
22	Correct	3 ms	4668 KB	Output is correct
23	Correct	7746 ms	30180 KB	Output is correct
24	Correct	2663 ms	30948 KB	Output is correct
25	Correct	1847 ms	16696 KB	Output is correct
26	Correct	2620 ms	21920 KB	Output is correct
27	Correct	2771 ms	21920 KB	Output is correct
28	Correct	88 ms	11944 KB	Output is correct
29	Correct	2213 ms	21512 KB	Output is correct
30	Correct	2025 ms	21176 KB	Output is correct
31	Correct	668 ms	18316 KB	Output is correct
32	Correct	769 ms	18296 KB	Output is correct
33	Correct	9297 ms	42476 KB	Output is correct
34	Correct	9241 ms	42460 KB	Output is correct
35	Correct	7129 ms	39440 KB	Output is correct
36	Correct	1801 ms	24944 KB	Output is correct
37	Correct	1776 ms	24872 KB	Output is correct
38	Correct	1983 ms	24924 KB	Output is correct