Submission #833095

#	Time	Username	Problem	Language	Result	Execution time	Memory
833095		annyeong1	Road Construction (JOI21_road_construction)	C++14	100 / 100	2707 ms	927192 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using p64x = pair<i64, int>;

static constexpr int digits = 19;
static constexpr i64 INF = 1e10;

struct seg {
  seg *l,*r;
  p64x mn;
  seg() : l(),r(),mn(INF, 0){}
  seg(p64x min_) : l(),r(),mn(min_){}
  seg(seg *s, seg *e) : l(s),r(e),mn(min(s->mn,e->mn)){}
  static seg init(int d = digits){
    if(d==0)return {};--d;
    auto c=new seg(init(d));
    return {c,c};
  }
  p64x get_min(int s, int e, int ll = 0, int rr = 1 << digits) {
    if (e<=ll||rr<=s)return {INF, 0};
    if (s<=ll&&rr<=e)return mn;
    int m=(ll+rr)/2;
    return min(l->get_min(s,e,ll,m),r->get_min(s,e,m,rr));
  }
  seg update(int i, i64 v, int d = digits) {
    if (d==0)return{{v,i}}; --d;
    if (i >> d & 1)return {l, new seg(r->update(i, v, d))};
    else return {new seg(l->update(i, v, d)), r};
  }
};
struct cpr {
  vector<p64x> v;
  void add(p64x x){v.push_back(x);}
  void build(){sort(v.begin(),v.end());}
  int get(p64x x){return lower_bound(v.begin(),v.end(), x)-v.begin();}
};
struct town{i64 x,y;};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,k; cin>>n>>k;
  vector<town>towns(n);
  for (auto &[x,y]:towns)cin >> x >> y;
  sort(towns.begin(), towns.end(),[&](const auto &l,const auto &r){return l.x<r.x;});
  cpr yc;
  for (int i=0;i<n;i++) {
    const auto &[x,y]=towns[i];
    yc.add({y, i});
  }
  yc.build();
  vector<seg> u(n + 1), d(n + 1);
  u[0]=seg::init();
  d[0]=seg::init();
  for(int i=0;i<n;i++) {
    const auto &[x,y]=towns[i];
    const int pos=yc.get({y,i});
    u[i + 1]=u[i].update(pos,-x + y);
    d[i + 1]=d[i].update(pos,-x - y);
  }
  priority_queue<p64x, vector<p64x>, greater<p64x>> que;
  const auto push = [&](const int i) {
    const auto &[x,y] = towns[i];
    const int pos = yc.get({y, i});
    const auto [um, ui] = u[i].get_min(pos, 1 << digits);
    const auto [dm, di] = d[i].get_min(0, pos);
    if (um == INF && dm == INF)return;
    if (um + x - y < dm + x + y) {
      que.push({um + x - y, i});
      u[i] = u[i].update(ui, INF);
    }else{
      que.push({dm + x + y, i});
      d[i] = d[i].update(di, INF);
    }
  };
  for (int i=0;i<n;i++)push(i);
  for (int i=0;i<k;i++) {
    const auto [c,j]=que.top();que.pop();
    cout<<c<<'\n'; push(j);
  } return 0;
}

Compilation message (stderr)

road_construction.cpp: In static member function 'static seg seg::init(int)':
road_construction.cpp:16:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   16 |     if(d==0)return {};--d;
      |     ^~
road_construction.cpp:16:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   16 |     if(d==0)return {};--d;
      |                       ^~
road_construction.cpp: In member function 'seg seg::update(int, i64, int)':
road_construction.cpp:27:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |     if (d==0)return{{v,i}}; --d;
      |     ^~
road_construction.cpp:27:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |     if (d==0)return{{v,i}}; --d;
      |                             ^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |   for (auto &[x,y]:towns)cin >> x >> y;
      |              ^
road_construction.cpp:48:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     const auto &[x,y]=towns[i];
      |                 ^
road_construction.cpp:56:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     const auto &[x,y]=towns[i];
      |                 ^
road_construction.cpp: In lambda function:
road_construction.cpp:63:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     const auto &[x,y] = towns[i];
      |                 ^
road_construction.cpp:65:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     const auto [um, ui] = u[i].get_min(pos, 1 << digits);
      |                ^
road_construction.cpp:66:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     const auto [dm, di] = d[i].get_min(0, pos);
      |                ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:78:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     const auto [c,j]=que.top();que.pop();
      |                ^

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