oj.uz

답안 #390679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390679 2021-04-16T13:43:59 Z PedroBigMan Road Construction (JOI21_road_construction) C++14
100 / 100
 8406 ms 38252 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);
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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