Submission #945812

#TimeUsernameProblemLanguageResultExecution timeMemory
945812kxdRoad Construction (JOI21_road_construction)C++17
0 / 100
150 ms7868 KiB
#include <bits/stdc++.h> //#define DEBUG 1106 #define int long long #define ll long long #define ld long double #define pb push_back #define p_q priority_queue #define m_p make_pair #define pii pair<int,int> #define endl '\n' #define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define FOR(i,a,b) for(int i = a; i <= b; i++) #define forn(i,n) for (int i = 0; i < n; i++) #define forn1(i,n) for (int i = 1; i <= n; i++) #define all(x) x.begin(),x.end() #define ft first #define sd second #define lowbit(x) (x&(-x)) #define chmax(x,y) x=max(x,y) #define chmin(x,y) x=min(x,y) #ifdef DEBUG #define debug(x) cout << #x << ": " << x << endl; #else #define debug(x) 1106; #endif using namespace std; const int N = 2e5+5; const int inf = 1e9; const int INF = 1e18; const int MOD = 1e9+7; int a[N]; signed main() { //INIT #ifdef DEBUG freopen("input.txt", "r", stdin); #endif /////////// int n, k; cin >> n >> k; int t; forn(i,n) cin >> a[i] >> t; sort(a,a+n); int lo = 0; int hi = a[n-1]-a[0]; int ans = -1; while (lo<=hi) { int mid = (lo+hi)/2; int t = 0; forn(i,n) { t += upper_bound(a+i+1,a+n,a[i]+mid)-(a+i+1); } //cout << "|| t: " << t << ", mid: " << mid << ", lo: " << lo << ", hi: " << hi << endl; if(t<k) { //ans = mid; lo = mid+1; } else { ans = mid; hi = mid-1; } //cout << "|| t: " << t << ", mid: " << mid << ", lo: " << lo << ", hi: " << hi << endl; } //cout << '>' << ans << endl; int x = ans; vector<int> v; forn(i,n) { int j = i+1; while(j<n && a[j]-a[i]<=x) { v.pb(a[j]-a[i]); j++; } } sort(all(v)); for(auto it: v) cout << it << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...