oj.uz

Submission #833095

# Submission time Handle Problem Language Result Execution time Memory
833095 2023-08-22T00:24:49 Z annyeong1 Road Construction (JOI21_road_construction) C++14
100 / 100
 2707 ms 927192 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 228756 KB Output is correct
2 Correct 473 ms 228760 KB Output is correct
3 Correct 426 ms 226936 KB Output is correct
4 Correct 400 ms 226960 KB Output is correct
5 Correct 446 ms 227624 KB Output is correct
6 Correct 5 ms 4820 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 924336 KB Output is correct
2 Correct 1439 ms 924260 KB Output is correct
3 Correct 368 ms 226824 KB Output is correct
4 Correct 969 ms 924132 KB Output is correct
5 Correct 1050 ms 924160 KB Output is correct
6 Correct 1030 ms 924300 KB Output is correct
7 Correct 1105 ms 923800 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1601 ms 702048 KB Output is correct
2 Correct 1418 ms 702172 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 664 ms 699876 KB Output is correct
5 Correct 968 ms 702308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1601 ms 702048 KB Output is correct
2 Correct 1418 ms 702172 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 664 ms 699876 KB Output is correct
5 Correct 968 ms 702308 KB Output is correct
6 Correct 1386 ms 702188 KB Output is correct
7 Correct 1410 ms 702084 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1411 ms 702064 KB Output is correct
11 Correct 655 ms 699936 KB Output is correct
12 Correct 962 ms 702412 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 228756 KB Output is correct
2 Correct 473 ms 228760 KB Output is correct
3 Correct 426 ms 226936 KB Output is correct
4 Correct 400 ms 226960 KB Output is correct
5 Correct 446 ms 227624 KB Output is correct
6 Correct 5 ms 4820 KB Output is correct
7 Correct 1666 ms 506200 KB Output is correct
8 Correct 1674 ms 506204 KB Output is correct
9 Correct 425 ms 227080 KB Output is correct
10 Correct 954 ms 505412 KB Output is correct
11 Correct 1136 ms 505284 KB Output is correct
12 Correct 753 ms 506088 KB Output is correct
13 Correct 901 ms 504740 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 228756 KB Output is correct
2 Correct 473 ms 228760 KB Output is correct
3 Correct 426 ms 226936 KB Output is correct
4 Correct 400 ms 226960 KB Output is correct
5 Correct 446 ms 227624 KB Output is correct
6 Correct 5 ms 4820 KB Output is correct
7 Correct 1504 ms 924336 KB Output is correct
8 Correct 1439 ms 924260 KB Output is correct
9 Correct 368 ms 226824 KB Output is correct
10 Correct 969 ms 924132 KB Output is correct
11 Correct 1050 ms 924160 KB Output is correct
12 Correct 1030 ms 924300 KB Output is correct
13 Correct 1105 ms 923800 KB Output is correct
14 Correct 1601 ms 702048 KB Output is correct
15 Correct 1418 ms 702172 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 664 ms 699876 KB Output is correct
18 Correct 968 ms 702308 KB Output is correct
19 Correct 1386 ms 702188 KB Output is correct
20 Correct 1410 ms 702084 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1411 ms 702064 KB Output is correct
24 Correct 655 ms 699936 KB Output is correct
25 Correct 962 ms 702412 KB Output is correct
26 Correct 1666 ms 506200 KB Output is correct
27 Correct 1674 ms 506204 KB Output is correct
28 Correct 425 ms 227080 KB Output is correct
29 Correct 954 ms 505412 KB Output is correct
30 Correct 1136 ms 505284 KB Output is correct
31 Correct 753 ms 506088 KB Output is correct
32 Correct 901 ms 504740 KB Output is correct
33 Correct 2675 ms 927104 KB Output is correct
34 Correct 2707 ms 927132 KB Output is correct
35 Correct 1859 ms 926388 KB Output is correct
36 Correct 1377 ms 927108 KB Output is correct
37 Correct 1362 ms 927192 KB Output is correct
38 Correct 1830 ms 925912 KB Output is correct