oj.uz

Submission #1032022

# Submission time Handle Problem Language Result Execution time Memory
1032022 2024-07-23T10:16:26 Z AdamGS Road Construction (JOI21_road_construction) C++17
100 / 100
 7159 ms 28744 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 11316 KB Output is correct
2 Correct 1221 ms 11204 KB Output is correct
3 Correct 1112 ms 11300 KB Output is correct
4 Correct 1116 ms 11308 KB Output is correct
5 Correct 985 ms 10036 KB Output is correct
6 Correct 15 ms 6492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6607 ms 25724 KB Output is correct
2 Correct 6661 ms 25796 KB Output is correct
3 Correct 1300 ms 11044 KB Output is correct
4 Correct 6385 ms 25456 KB Output is correct
5 Correct 6381 ms 25616 KB Output is correct
6 Correct 6365 ms 25716 KB Output is correct
7 Correct 6165 ms 25064 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2915 ms 24640 KB Output is correct
2 Correct 3033 ms 24636 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 3334 ms 22352 KB Output is correct
5 Correct 2728 ms 24880 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2915 ms 24640 KB Output is correct
2 Correct 3033 ms 24636 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 3334 ms 22352 KB Output is correct
5 Correct 2728 ms 24880 KB Output is correct
6 Correct 3092 ms 24636 KB Output is correct
7 Correct 2926 ms 24636 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 3130 ms 24636 KB Output is correct
11 Correct 3439 ms 22348 KB Output is correct
12 Correct 3002 ms 24880 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 11316 KB Output is correct
2 Correct 1221 ms 11204 KB Output is correct
3 Correct 1112 ms 11300 KB Output is correct
4 Correct 1116 ms 11308 KB Output is correct
5 Correct 985 ms 10036 KB Output is correct
6 Correct 15 ms 6492 KB Output is correct
7 Correct 3325 ms 19252 KB Output is correct
8 Correct 3310 ms 19224 KB Output is correct
9 Correct 1145 ms 11284 KB Output is correct
10 Correct 3116 ms 18712 KB Output is correct
11 Correct 2764 ms 17348 KB Output is correct
12 Correct 2960 ms 19204 KB Output is correct
13 Correct 3920 ms 19476 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 11316 KB Output is correct
2 Correct 1221 ms 11204 KB Output is correct
3 Correct 1112 ms 11300 KB Output is correct
4 Correct 1116 ms 11308 KB Output is correct
5 Correct 985 ms 10036 KB Output is correct
6 Correct 15 ms 6492 KB Output is correct
7 Correct 6607 ms 25724 KB Output is correct
8 Correct 6661 ms 25796 KB Output is correct
9 Correct 1300 ms 11044 KB Output is correct
10 Correct 6385 ms 25456 KB Output is correct
11 Correct 6381 ms 25616 KB Output is correct
12 Correct 6365 ms 25716 KB Output is correct
13 Correct 6165 ms 25064 KB Output is correct
14 Correct 2915 ms 24640 KB Output is correct
15 Correct 3033 ms 24636 KB Output is correct
16 Correct 1 ms 6744 KB Output is correct
17 Correct 3334 ms 22352 KB Output is correct
18 Correct 2728 ms 24880 KB Output is correct
19 Correct 3092 ms 24636 KB Output is correct
20 Correct 2926 ms 24636 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 3130 ms 24636 KB Output is correct
24 Correct 3439 ms 22348 KB Output is correct
25 Correct 3002 ms 24880 KB Output is correct
26 Correct 3325 ms 19252 KB Output is correct
27 Correct 3310 ms 19224 KB Output is correct
28 Correct 1145 ms 11284 KB Output is correct
29 Correct 3116 ms 18712 KB Output is correct
30 Correct 2764 ms 17348 KB Output is correct
31 Correct 2960 ms 19204 KB Output is correct
32 Correct 3920 ms 19476 KB Output is correct
33 Correct 7159 ms 28704 KB Output is correct
34 Correct 6825 ms 28704 KB Output is correct
35 Correct 5852 ms 27936 KB Output is correct
36 Correct 4543 ms 28744 KB Output is correct
37 Correct 4496 ms 28704 KB Output is correct
38 Correct 5833 ms 27412 KB Output is correct