Submission #1032022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032022		AdamGS	Road Construction (JOI21_road_construction)	C++17	100 / 100	7159 ms	28744 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e10+7;
const int LIM=25e4+7;
vector<ll>wyn;
pair<ll,ll>T[LIM], P[LIM];
ll jaki[LIM], N=1, n, k;
pair<ll,ll>tr[4*LIM];
void upd(int v, ll x) {
  v+=N;
  tr[v]={x, v-N};
  v/=2;
  while(v) {
    tr[v]=min(tr[2*v], tr[2*v+1]);
    v/=2;
  }
}
ll cnt(int l, int r) {
  l+=N; r+=N;
  pair<ll,ll>ans=min(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=min(ans, tr[l+1]);
    if(r%2==1) ans=min(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans.nd;
}
void cl() {
  rep(i, 2*N) tr[i]={INF, INF};
  rep(i, n) tr[N+i].nd=i;
  for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
}
void check(ll x) {
  wyn.clear();
  cl();
  rep(xd, n) {
    ll i=P[xd].nd;
    vector<pair<ll,ll>>A;
    while(wyn.size()<k) {
      ll a=cnt(0, jaki[i]);
      if(tr[N+a].st==INF) break;
      ll b=T[i].st+T[i].nd+tr[N+a].st;
      if(b>x) break;
      wyn.pb(b);
      A.pb({a, tr[N+a].st});
      upd(a, INF);
    }
    for(auto j : A) upd(j.st, j.nd);
    upd(jaki[i], -T[i].st-T[i].nd);
  }
  cl();
  rep(xd, n) {
    ll i=P[xd].nd;
    vector<pair<ll,ll>>A;
    while(wyn.size()<k) {
      ll a=cnt(jaki[i], n-1);
      if(tr[N+a].st==INF) break;
      ll b=T[i].st-T[i].nd+tr[N+a].st;
      if(b>x) break;
      wyn.pb(b);
      A.pb({a, tr[N+a].st});
      upd(a, INF);
    }
    for(auto j : A) upd(j.st, j.nd);
    upd(jaki[i], -T[i].st+T[i].nd);
  }
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  while(N<n) N*=2;
  rep(i, n) cin >> T[i].st >> T[i].nd;
  rep(i, n) P[i]={T[i].nd, i};
  sort(P, P+n);
  rep(i, n) jaki[P[i].nd]=i;
  rep(i, n) P[i]={T[i].st, i};
  sort(P, P+n);
  ll po=0, ko=INF;
  while(po<ko) {
    ll sr=(po+ko+1)/2;
    check(sr);
    if(wyn.size()>=k) ko=sr-1; else po=sr;
  }
  check(po);
  while(wyn.size()<k) wyn.pb(po+1);
  sort(all(wyn));
  for(auto i : wyn) cout << i << '\n';
}

Compilation message (stderr)

road_construction.cpp: In function 'void check(ll)':
road_construction.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   46 |     while(wyn.size()<k) {
      |           ~~~~~~~~~~^~
road_construction.cpp:62:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   62 |     while(wyn.size()<k) {
      |           ~~~~~~~~~~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:89:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   89 |     if(wyn.size()>=k) ko=sr-1; else po=sr;
      |        ~~~~~~~~~~^~~
road_construction.cpp:92:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   92 |   while(wyn.size()<k) wyn.pb(po+1);
      |         ~~~~~~~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35