oj.uz

답안 #390678

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

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

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

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

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

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

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