oj.uz

Submission #1025288

# Submission time Handle Problem Language Result Execution time Memory
1025288 2024-07-16T19:17:55 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145452 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#pragma GCC optimize("Ofast,unroll-loops")
// #define int ll
#define pli pair <ll,int>
#define pll pair <ll,ll>
using namespace std;
 
const int N = 3e5 + 3;
const ll inf = 1e18;
pli t[2][3*N];
int x[N],y[N],yy[N],n,k,L,R;
multiset <ll> st[2][3*N];
pii arr[N];
vector <ll> answ;
ll oldval,newval,w1;
int idx,v1,v2,id;
bool z,ID;
pli res;
 
void upd(int h,int l,int r){
  if (l == r){
    if (!z) st[ID][l].erase(st[ID][l].find(oldval));
    st[ID][l].insert(newval);
    t[ID][h] = {*--st[ID][l].end(),l};
    return;
  }
 
  if (idx > (l + r)/2) upd(right);
  else upd(left);
  t[ID][h] = max(t[ID][h*2],t[ID][h*2 + 1]);
}
 
void build(int h,int l,int r){
  t[1][h] = t[0][h] = {-inf,0};
  if (l == r) {
    st[1][l].clear();
    st[0][l].clear();
    return;
  }
  build(left);
  build(right);
}
 
pli get(int h,int l,int r){
  if (r < L || R < l) return {-inf,0};
  if (L <= l && r <= R) return t[ID][h];
  return max(get(left),get(right));
}
 
int count(ll w,bool zz){
 
  build(1,1,n);
  int tot = 0,i,j;
 
  for (i = 1; i <= n; i++){
    if (tot > k) return tot;
    vector <pair <pii,pll> > roll;
 
    id = arr[i].s; v1 = x[id] + y[id];
    while (tot <= k){
      L = 1; R = yy[id]; ID = 0;
      res = get(1,1,n);
      w1 = v1 - res.f;
      if (w1 > w) break;
      if (zz) answ.pb(w1);
 
      tot += 1;
      if (tot > k) return tot;
      roll.pb({{0,res.s},{res.f,-inf}});
      idx = res.s; oldval = res.f; newval = -inf;
      z = 0; ID = 0;
      upd(1,1,n);
    }
 
    v2 = x[id] - y[id];
    while (tot <= k){
      L = yy[id] + 1; R = n; ID = 1;
      res = get(1,1,n);
      w1 = v2 - res.f;
      if (w1 > w) break;
      if (zz) answ.pb(w1);
 
      tot += 1;
      if (tot > k) return tot;
      roll.pb({{1,res.s},{res.f,-inf}});
      oldval = res.f;
      newval = -inf;
      idx = res.s;
      z = 0; ID = 1;
      upd(1,1,n);
    }
    
    for (j = roll.size() - 1; j >= 0; j--){
      oldval = roll[j].s.s;
      newval = roll[j].s.f;
      idx = roll[j].f.s;
      z = 0; ID = roll[j].f.f;
      upd(1,1,n);
    }
 
    oldval = -inf;
    newval = v1;
    idx = yy[id];
    z = 1; ID = 0;
    upd(1,1,n);
 
    newval = v2; ID = 1;
    upd(1,1,n);
  }
 
  return tot;
}
 
signed main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
  cin>>n>>k;
  
  vector <int> vec;
  for (int i = 1; i <= n; i++){
    cin >> x[i] >> y[i];
    vec.pb(y[i]);
  }
  sort(vec.begin(),vec.end());
  map <int,int> mp;
  int val = 0;
  for (int i=0;i<vec.size();i++){
    if (!i || vec[i] != vec[i - 1]) ++val;
    mp[vec[i]] = val;
  }
 
  for (int i = 1; i<= n; i++){
    yy[i] = mp[y[i]];
    arr[i] = {x[i],i};
  }
  sort(arr+1,arr+n+1);
 
  ll l = 0,r = 4e9,res = -1;
  while (l <= r){
    ll mid = (l + r) >> 1;
    //umciresi w iseti rom w ze naklebi an toli wonis wiboebis raodenoba >= k ze
  
    if (count(mid,0) >= k) {
      res = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
 
  int cnt1 = count(res - 1,1);
  sort(answ.begin(),answ.end());
  for (int i = 1; i <= k - cnt1; i++)
    answ.pb(res);
    
  for (ll x: answ)
    cout<<x<<endl;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:135:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 95384 KB Output is correct
2 Correct 2454 ms 95440 KB Output is correct
3 Correct 2580 ms 95440 KB Output is correct
4 Correct 2629 ms 93604 KB Output is correct
5 Correct 2714 ms 92284 KB Output is correct
6 Correct 36 ms 90784 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8621 ms 135088 KB Output is correct
2 Correct 8572 ms 136468 KB Output is correct
3 Correct 2904 ms 95320 KB Output is correct
4 Correct 8558 ms 136824 KB Output is correct
5 Correct 8326 ms 136928 KB Output is correct
6 Correct 7868 ms 136928 KB Output is correct
7 Correct 7293 ms 136396 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6331 ms 145256 KB Output is correct
2 Correct 5840 ms 145264 KB Output is correct
3 Correct 16 ms 90716 KB Output is correct
4 Correct 2116 ms 133484 KB Output is correct
5 Correct 3959 ms 133520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6331 ms 145256 KB Output is correct
2 Correct 5840 ms 145264 KB Output is correct
3 Correct 16 ms 90716 KB Output is correct
4 Correct 2116 ms 133484 KB Output is correct
5 Correct 3959 ms 133520 KB Output is correct
6 Correct 6268 ms 145140 KB Output is correct
7 Correct 6339 ms 145220 KB Output is correct
8 Correct 13 ms 90716 KB Output is correct
9 Correct 13 ms 90704 KB Output is correct
10 Correct 6496 ms 143824 KB Output is correct
11 Correct 1724 ms 133484 KB Output is correct
12 Correct 3998 ms 133436 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 95384 KB Output is correct
2 Correct 2454 ms 95440 KB Output is correct
3 Correct 2580 ms 95440 KB Output is correct
4 Correct 2629 ms 93604 KB Output is correct
5 Correct 2714 ms 92284 KB Output is correct
6 Correct 36 ms 90784 KB Output is correct
7 Correct 7537 ms 119744 KB Output is correct
8 Correct 7457 ms 119392 KB Output is correct
9 Correct 2275 ms 95616 KB Output is correct
10 Correct 6206 ms 117980 KB Output is correct
11 Correct 4972 ms 117584 KB Output is correct
12 Correct 5478 ms 114964 KB Output is correct
13 Correct 6578 ms 113528 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 95384 KB Output is correct
2 Correct 2454 ms 95440 KB Output is correct
3 Correct 2580 ms 95440 KB Output is correct
4 Correct 2629 ms 93604 KB Output is correct
5 Correct 2714 ms 92284 KB Output is correct
6 Correct 36 ms 90784 KB Output is correct
7 Correct 8621 ms 135088 KB Output is correct
8 Correct 8572 ms 136468 KB Output is correct
9 Correct 2904 ms 95320 KB Output is correct
10 Correct 8558 ms 136824 KB Output is correct
11 Correct 8326 ms 136928 KB Output is correct
12 Correct 7868 ms 136928 KB Output is correct
13 Correct 7293 ms 136396 KB Output is correct
14 Correct 6331 ms 145256 KB Output is correct
15 Correct 5840 ms 145264 KB Output is correct
16 Correct 16 ms 90716 KB Output is correct
17 Correct 2116 ms 133484 KB Output is correct
18 Correct 3959 ms 133520 KB Output is correct
19 Correct 6268 ms 145140 KB Output is correct
20 Correct 6339 ms 145220 KB Output is correct
21 Correct 13 ms 90716 KB Output is correct
22 Correct 13 ms 90704 KB Output is correct
23 Correct 6496 ms 143824 KB Output is correct
24 Correct 1724 ms 133484 KB Output is correct
25 Correct 3998 ms 133436 KB Output is correct
26 Correct 7537 ms 119744 KB Output is correct
27 Correct 7457 ms 119392 KB Output is correct
28 Correct 2275 ms 95616 KB Output is correct
29 Correct 6206 ms 117980 KB Output is correct
30 Correct 4972 ms 117584 KB Output is correct
31 Correct 5478 ms 114964 KB Output is correct
32 Correct 6578 ms 113528 KB Output is correct
33 Execution timed out 10029 ms 145452 KB Time limit exceeded
34 Halted 0 ms 0 KB -