oj.uz

Submission #392791

# Submission time Handle Problem Language Result Execution time Memory
392791 2021-04-21T16:57:16 Z AmineWeslati Road Construction (JOI21_road_construction) C++14
100 / 100
 6678 ms 26792 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 4e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

int N,K;
ll X[MX],Y[MX];
vi y;
ll mp[MX]; //compressed y-coord

bool cmp(int i, int j){
	return X[i]<X[j];
}

bool cmp2(int i, int j){
	return Y[i]<Y[j];
}
void adjustXY(){
	FOR(i,0,N){
		int nwx=X[i]-Y[i],nwy=X[i]+Y[i];
		X[i]=nwx,Y[i]=nwy;

		y.pb(i);
	}

	vi vec(N);
	iota(all(vec),0);
	sort(all(vec),cmp);

	int nwx[N],nwy[N];
	FOR(i,0,N){
		nwx[i]=X[vec[i]];
		nwy[i]=Y[vec[i]];
	}
	FOR(i,0,N){
		X[i]=nwx[i];
		Y[i]=nwy[i];
	}

	sort(all(y),cmp2);
	FOR(i,0,N) mp[y[i]]=i+1,y[i]=Y[y[i]];
}


vi t(MX); 
void upd(int i, int v){
	for(;i<MX; i+=i&-i){
		t[i]+=v; 
	}
}
int get(int i){
	int ans=0;
	for(;i;i-=i&-i) ans+=t[i];
	return ans;
}

ll query(ll l, ll r){
	l=lower_bound(all(y),l)-y.begin()+1;
	r=upper_bound(all(y),r)-y.begin();
	if(l>r) return 0;
	return get(r)-get(l-1);
}


ll solve(ll D){
	FOR(i,0,MX) t[i]=0;

	int j=0;
	ll ans=0;
	FOR(i,0,N){
		while(j<i && X[i]-X[j]>D){
			upd(mp[j],-1); 
			j++;
		}

		ans+=query(Y[i]-D,Y[i]+D);

		upd(mp[i],1);
	}
	return ans;
}

V<ll> ans; 
void solve2(ll D){
	int j=0;
	set<pair<ll,ll>>s;
	FOR(i,0,N){
		while(j<i && X[i]-X[j]>D){
			s.erase({Y[j],X[j]});
			j++;
		}

		pair<ll,ll> p={Y[i]-D,-INF};
		auto it=lower_bound(all(s),p);
		while(it!=s.end()){
			ll yy=(*it).fi,xx=(*it).se;
			if(yy-Y[i]>D) break;

			ans.pb(max(abs(X[i]-xx),abs(Y[i]-yy)));
			assert(ans.back()<=D);

			it++;
		}

		s.insert({Y[i],X[i]});
	}

}

int main() {
    boost; IO();
    	
    cin>>N>>K;
    FOR(i,0,N) cin>>X[i]>>Y[i];

    adjustXY();


    ll l=0,r=5e9,D;
    while(l<=r){
    	ll m=(l+r)/2;
    	if(solve(m)>=K) D=m,r=m-1;
    	else l=m+1;
    }


    solve2(D);
    sort(all(ans));
    FOR(i,0,K) cout << ans[i] << endl;


    return 0;
}
//Change your approach

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:176:11: warning: 'D' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |     solve2(D);
      |     ~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6580 KB Output is correct
2 Correct 72 ms 6828 KB Output is correct
3 Correct 65 ms 6720 KB Output is correct
4 Correct 63 ms 6720 KB Output is correct
5 Correct 64 ms 5500 KB Output is correct
6 Correct 14 ms 1996 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1783 ms 14796 KB Output is correct
2 Correct 1709 ms 17844 KB Output is correct
3 Correct 61 ms 6584 KB Output is correct
4 Correct 1681 ms 18860 KB Output is correct
5 Correct 1627 ms 19780 KB Output is correct
6 Correct 1663 ms 19888 KB Output is correct
7 Correct 1575 ms 18980 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3255 ms 11712 KB Output is correct
2 Correct 3221 ms 16864 KB Output is correct
3 Correct 8 ms 1868 KB Output is correct
4 Correct 1611 ms 16688 KB Output is correct
5 Correct 5298 ms 21176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3255 ms 11712 KB Output is correct
2 Correct 3221 ms 16864 KB Output is correct
3 Correct 8 ms 1868 KB Output is correct
4 Correct 1611 ms 16688 KB Output is correct
5 Correct 5298 ms 21176 KB Output is correct
6 Correct 3357 ms 16848 KB Output is correct
7 Correct 3510 ms 16800 KB Output is correct
8 Correct 8 ms 1868 KB Output is correct
9 Correct 8 ms 1868 KB Output is correct
10 Correct 3360 ms 16932 KB Output is correct
11 Correct 1615 ms 16716 KB Output is correct
12 Correct 3697 ms 17104 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6580 KB Output is correct
2 Correct 72 ms 6828 KB Output is correct
3 Correct 65 ms 6720 KB Output is correct
4 Correct 63 ms 6720 KB Output is correct
5 Correct 64 ms 5500 KB Output is correct
6 Correct 14 ms 1996 KB Output is correct
7 Correct 1921 ms 9912 KB Output is correct
8 Correct 1900 ms 11872 KB Output is correct
9 Correct 63 ms 6720 KB Output is correct
10 Correct 1312 ms 11180 KB Output is correct
11 Correct 1236 ms 11096 KB Output is correct
12 Correct 1961 ms 13412 KB Output is correct
13 Correct 1499 ms 12292 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6580 KB Output is correct
2 Correct 72 ms 6828 KB Output is correct
3 Correct 65 ms 6720 KB Output is correct
4 Correct 63 ms 6720 KB Output is correct
5 Correct 64 ms 5500 KB Output is correct
6 Correct 14 ms 1996 KB Output is correct
7 Correct 1783 ms 14796 KB Output is correct
8 Correct 1709 ms 17844 KB Output is correct
9 Correct 61 ms 6584 KB Output is correct
10 Correct 1681 ms 18860 KB Output is correct
11 Correct 1627 ms 19780 KB Output is correct
12 Correct 1663 ms 19888 KB Output is correct
13 Correct 1575 ms 18980 KB Output is correct
14 Correct 3255 ms 11712 KB Output is correct
15 Correct 3221 ms 16864 KB Output is correct
16 Correct 8 ms 1868 KB Output is correct
17 Correct 1611 ms 16688 KB Output is correct
18 Correct 5298 ms 21176 KB Output is correct
19 Correct 3357 ms 16848 KB Output is correct
20 Correct 3510 ms 16800 KB Output is correct
21 Correct 8 ms 1868 KB Output is correct
22 Correct 8 ms 1868 KB Output is correct
23 Correct 3360 ms 16932 KB Output is correct
24 Correct 1615 ms 16716 KB Output is correct
25 Correct 3697 ms 17104 KB Output is correct
26 Correct 1921 ms 9912 KB Output is correct
27 Correct 1900 ms 11872 KB Output is correct
28 Correct 63 ms 6720 KB Output is correct
29 Correct 1312 ms 11180 KB Output is correct
30 Correct 1236 ms 11096 KB Output is correct
31 Correct 1961 ms 13412 KB Output is correct
32 Correct 1499 ms 12292 KB Output is correct
33 Correct 5032 ms 20648 KB Output is correct
34 Correct 5078 ms 20648 KB Output is correct
35 Correct 3454 ms 20016 KB Output is correct
36 Correct 6432 ms 26792 KB Output is correct
37 Correct 6678 ms 26668 KB Output is correct
38 Correct 4969 ms 21144 KB Output is correct