Submission #390679

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390679	2021-04-16T13:43:59 Z	PedroBigMan	Road Construction (JOI21_road_construction)	C++14	100 / 100	8406 ms	38252 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<<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

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	141 ms	15864 KB	Output is correct
2	Correct	121 ms	15692 KB	Output is correct
3	Correct	94 ms	15760 KB	Output is correct
4	Correct	90 ms	15896 KB	Output is correct
5	Correct	91 ms	14636 KB	Output is correct
6	Correct	10 ms	8780 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3559 ms	38200 KB	Output is correct
2	Correct	3558 ms	38116 KB	Output is correct
3	Correct	81 ms	15664 KB	Output is correct
4	Correct	3240 ms	38052 KB	Output is correct
5	Correct	2476 ms	38252 KB	Output is correct
6	Correct	2346 ms	38036 KB	Output is correct
7	Correct	2554 ms	38068 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7798 ms	30356 KB	Output is correct
2	Correct	7487 ms	30296 KB	Output is correct
3	Correct	8 ms	8524 KB	Output is correct
4	Correct	3155 ms	30208 KB	Output is correct
5	Correct	1852 ms	20448 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7798 ms	30356 KB	Output is correct
2	Correct	7487 ms	30296 KB	Output is correct
3	Correct	8 ms	8524 KB	Output is correct
4	Correct	3155 ms	30208 KB	Output is correct
5	Correct	1852 ms	20448 KB	Output is correct
6	Correct	7574 ms	30184 KB	Output is correct
7	Correct	7881 ms	30336 KB	Output is correct
8	Correct	7 ms	8580 KB	Output is correct
9	Correct	6 ms	8524 KB	Output is correct
10	Correct	7502 ms	29748 KB	Output is correct
11	Correct	3423 ms	30404 KB	Output is correct
12	Correct	2095 ms	20448 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	15864 KB	Output is correct
2	Correct	121 ms	15692 KB	Output is correct
3	Correct	94 ms	15760 KB	Output is correct
4	Correct	90 ms	15896 KB	Output is correct
5	Correct	91 ms	14636 KB	Output is correct
6	Correct	10 ms	8780 KB	Output is correct
7	Correct	2745 ms	25764 KB	Output is correct
8	Correct	2747 ms	25728 KB	Output is correct
9	Correct	92 ms	15884 KB	Output is correct
10	Correct	2297 ms	25304 KB	Output is correct
11	Correct	2072 ms	24960 KB	Output is correct
12	Correct	678 ms	22108 KB	Output is correct
13	Correct	702 ms	22104 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	15864 KB	Output is correct
2	Correct	121 ms	15692 KB	Output is correct
3	Correct	94 ms	15760 KB	Output is correct
4	Correct	90 ms	15896 KB	Output is correct
5	Correct	91 ms	14636 KB	Output is correct
6	Correct	10 ms	8780 KB	Output is correct
7	Correct	3559 ms	38200 KB	Output is correct
8	Correct	3558 ms	38116 KB	Output is correct
9	Correct	81 ms	15664 KB	Output is correct
10	Correct	3240 ms	38052 KB	Output is correct
11	Correct	2476 ms	38252 KB	Output is correct
12	Correct	2346 ms	38036 KB	Output is correct
13	Correct	2554 ms	38068 KB	Output is correct
14	Correct	7798 ms	30356 KB	Output is correct
15	Correct	7487 ms	30296 KB	Output is correct
16	Correct	8 ms	8524 KB	Output is correct
17	Correct	3155 ms	30208 KB	Output is correct
18	Correct	1852 ms	20448 KB	Output is correct
19	Correct	7574 ms	30184 KB	Output is correct
20	Correct	7881 ms	30336 KB	Output is correct
21	Correct	7 ms	8580 KB	Output is correct
22	Correct	6 ms	8524 KB	Output is correct
23	Correct	7502 ms	29748 KB	Output is correct
24	Correct	3423 ms	30404 KB	Output is correct
25	Correct	2095 ms	20448 KB	Output is correct
26	Correct	2745 ms	25764 KB	Output is correct
27	Correct	2747 ms	25728 KB	Output is correct
28	Correct	92 ms	15884 KB	Output is correct
29	Correct	2297 ms	25304 KB	Output is correct
30	Correct	2072 ms	24960 KB	Output is correct
31	Correct	678 ms	22108 KB	Output is correct
32	Correct	702 ms	22104 KB	Output is correct
33	Correct	8406 ms	38036 KB	Output is correct
34	Correct	8305 ms	38016 KB	Output is correct
35	Correct	6936 ms	35552 KB	Output is correct
36	Correct	1747 ms	28740 KB	Output is correct
37	Correct	1779 ms	28784 KB	Output is correct
38	Correct	1955 ms	28704 KB	Output is correct