oj.uz

Submission #389059

# Submission time Handle Problem Language Result Execution time Memory
389059 2021-04-13T14:57:40 Z PedroBigMan Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 33300 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;
	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:159:7: warning: unused variable 'dx' [-Wunused-variable]
  159 |    ll dx,dy; dy = it->ff-y;
      |       ^~
road_construction.cpp:169: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]
  169 |  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 94 ms 7520 KB Output is correct
2 Correct 94 ms 7448 KB Output is correct
3 Correct 87 ms 7504 KB Output is correct
4 Correct 85 ms 7652 KB Output is correct
5 Correct 84 ms 6432 KB Output is correct
6 Correct 6 ms 460 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4045 ms 33280 KB Output is correct
2 Correct 3997 ms 33032 KB Output is correct
3 Correct 77 ms 7456 KB Output is correct
4 Correct 3470 ms 33248 KB Output is correct
5 Correct 2383 ms 33300 KB Output is correct
6 Correct 2456 ms 33128 KB Output is correct
7 Correct 2381 ms 33160 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8654 ms 25344 KB Output is correct
2 Correct 8515 ms 29128 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2513 ms 26816 KB Output is correct
5 Correct 1902 ms 17612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8654 ms 25344 KB Output is correct
2 Correct 8515 ms 29128 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2513 ms 26816 KB Output is correct
5 Correct 1902 ms 17612 KB Output is correct
6 Correct 8572 ms 29192 KB Output is correct
7 Correct 8356 ms 29028 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 8221 ms 28380 KB Output is correct
11 Correct 2510 ms 26940 KB Output is correct
12 Correct 1950 ms 17508 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7520 KB Output is correct
2 Correct 94 ms 7448 KB Output is correct
3 Correct 87 ms 7504 KB Output is correct
4 Correct 85 ms 7652 KB Output is correct
5 Correct 84 ms 6432 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 2627 ms 20444 KB Output is correct
8 Correct 2650 ms 20400 KB Output is correct
9 Correct 87 ms 7644 KB Output is correct
10 Correct 2347 ms 20096 KB Output is correct
11 Correct 2246 ms 19856 KB Output is correct
12 Correct 648 ms 15828 KB Output is correct
13 Correct 731 ms 15944 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7520 KB Output is correct
2 Correct 94 ms 7448 KB Output is correct
3 Correct 87 ms 7504 KB Output is correct
4 Correct 85 ms 7652 KB Output is correct
5 Correct 84 ms 6432 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 4045 ms 33280 KB Output is correct
8 Correct 3997 ms 33032 KB Output is correct
9 Correct 77 ms 7456 KB Output is correct
10 Correct 3470 ms 33248 KB Output is correct
11 Correct 2383 ms 33300 KB Output is correct
12 Correct 2456 ms 33128 KB Output is correct
13 Correct 2381 ms 33160 KB Output is correct
14 Correct 8654 ms 25344 KB Output is correct
15 Correct 8515 ms 29128 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 2513 ms 26816 KB Output is correct
18 Correct 1902 ms 17612 KB Output is correct
19 Correct 8572 ms 29192 KB Output is correct
20 Correct 8356 ms 29028 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 8221 ms 28380 KB Output is correct
24 Correct 2510 ms 26940 KB Output is correct
25 Correct 1950 ms 17508 KB Output is correct
26 Correct 2627 ms 20444 KB Output is correct
27 Correct 2650 ms 20400 KB Output is correct
28 Correct 87 ms 7644 KB Output is correct
29 Correct 2347 ms 20096 KB Output is correct
30 Correct 2246 ms 19856 KB Output is correct
31 Correct 648 ms 15828 KB Output is correct
32 Correct 731 ms 15944 KB Output is correct
33 Execution timed out 10040 ms 32380 KB Time limit exceeded
34 Halted 0 ms 0 KB -