oj.uz

Submission #390675

# Submission time Handle Problem Language Result Execution time Memory
390675 2021-04-16T13:40:00 Z PedroBigMan Road Construction (JOI21_road_construction) C++14
100 / 100
 8916 ms 298788 KB 
#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);
    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<<25LL); 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:160:7: warning: unused variable 'dx' [-Wunused-variable]
  160 |    ll dx,dy; dy = it->ff-y;
      |       ^~
road_construction.cpp:170: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]
  170 |  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 267 ms 271436 KB Output is correct
2 Correct 269 ms 271364 KB Output is correct
3 Correct 276 ms 271500 KB Output is correct
4 Correct 250 ms 271424 KB Output is correct
5 Correct 251 ms 270320 KB Output is correct
6 Correct 169 ms 264292 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3713 ms 296732 KB Output is correct
2 Correct 3917 ms 296892 KB Output is correct
3 Correct 248 ms 271336 KB Output is correct
4 Correct 3628 ms 296616 KB Output is correct
5 Correct 3579 ms 296656 KB Output is correct
6 Correct 3534 ms 296940 KB Output is correct
7 Correct 2674 ms 296868 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7664 ms 290976 KB Output is correct
2 Correct 8018 ms 290956 KB Output is correct
3 Correct 167 ms 264132 KB Output is correct
4 Correct 3529 ms 288824 KB Output is correct
5 Correct 2083 ms 281492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7664 ms 290976 KB Output is correct
2 Correct 8018 ms 290956 KB Output is correct
3 Correct 167 ms 264132 KB Output is correct
4 Correct 3529 ms 288824 KB Output is correct
5 Correct 2083 ms 281492 KB Output is correct
6 Correct 7823 ms 290896 KB Output is correct
7 Correct 7890 ms 290916 KB Output is correct
8 Correct 168 ms 264132 KB Output is correct
9 Correct 168 ms 264296 KB Output is correct
10 Correct 7447 ms 290252 KB Output is correct
11 Correct 3525 ms 288856 KB Output is correct
12 Correct 2067 ms 281396 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 271436 KB Output is correct
2 Correct 269 ms 271364 KB Output is correct
3 Correct 276 ms 271500 KB Output is correct
4 Correct 250 ms 271424 KB Output is correct
5 Correct 251 ms 270320 KB Output is correct
6 Correct 169 ms 264292 KB Output is correct
7 Correct 3023 ms 283372 KB Output is correct
8 Correct 3128 ms 283368 KB Output is correct
9 Correct 268 ms 271532 KB Output is correct
10 Correct 2848 ms 283028 KB Output is correct
11 Correct 2531 ms 282620 KB Output is correct
12 Correct 814 ms 279736 KB Output is correct
13 Correct 878 ms 279864 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 271436 KB Output is correct
2 Correct 269 ms 271364 KB Output is correct
3 Correct 276 ms 271500 KB Output is correct
4 Correct 250 ms 271424 KB Output is correct
5 Correct 251 ms 270320 KB Output is correct
6 Correct 169 ms 264292 KB Output is correct
7 Correct 3713 ms 296732 KB Output is correct
8 Correct 3917 ms 296892 KB Output is correct
9 Correct 248 ms 271336 KB Output is correct
10 Correct 3628 ms 296616 KB Output is correct
11 Correct 3579 ms 296656 KB Output is correct
12 Correct 3534 ms 296940 KB Output is correct
13 Correct 2674 ms 296868 KB Output is correct
14 Correct 7664 ms 290976 KB Output is correct
15 Correct 8018 ms 290956 KB Output is correct
16 Correct 167 ms 264132 KB Output is correct
17 Correct 3529 ms 288824 KB Output is correct
18 Correct 2083 ms 281492 KB Output is correct
19 Correct 7823 ms 290896 KB Output is correct
20 Correct 7890 ms 290916 KB Output is correct
21 Correct 168 ms 264132 KB Output is correct
22 Correct 168 ms 264296 KB Output is correct
23 Correct 7447 ms 290252 KB Output is correct
24 Correct 3525 ms 288856 KB Output is correct
25 Correct 2067 ms 281396 KB Output is correct
26 Correct 3023 ms 283372 KB Output is correct
27 Correct 3128 ms 283368 KB Output is correct
28 Correct 268 ms 271532 KB Output is correct
29 Correct 2848 ms 283028 KB Output is correct
30 Correct 2531 ms 282620 KB Output is correct
31 Correct 814 ms 279736 KB Output is correct
32 Correct 878 ms 279864 KB Output is correct
33 Correct 8871 ms 298752 KB Output is correct
34 Correct 8916 ms 298788 KB Output is correct
35 Correct 7616 ms 296300 KB Output is correct
36 Correct 1938 ms 289748 KB Output is correct
37 Correct 1944 ms 289404 KB Output is correct
38 Correct 2047 ms 289864 KB Output is correct