oj.uz

Submission #1025290

# Submission time Handle Problem Language Result Execution time Memory
1025290 2024-07-16T19:19:07 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
59 / 100
 10000 ms 145572 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 target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
// #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:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3211 ms 95388 KB Output is correct
2 Correct 3029 ms 91380 KB Output is correct
3 Correct 3087 ms 95376 KB Output is correct
4 Correct 3312 ms 95608 KB Output is correct
5 Correct 3132 ms 94280 KB Output is correct
6 Correct 40 ms 90716 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10067 ms 133496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7226 ms 145232 KB Output is correct
2 Correct 6432 ms 145468 KB Output is correct
3 Correct 14 ms 90712 KB Output is correct
4 Correct 2694 ms 133992 KB Output is correct
5 Correct 4315 ms 133856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7226 ms 145232 KB Output is correct
2 Correct 6432 ms 145468 KB Output is correct
3 Correct 14 ms 90712 KB Output is correct
4 Correct 2694 ms 133992 KB Output is correct
5 Correct 4315 ms 133856 KB Output is correct
6 Correct 7254 ms 145356 KB Output is correct
7 Correct 7407 ms 145572 KB Output is correct
8 Correct 14 ms 90716 KB Output is correct
9 Correct 12 ms 90712 KB Output is correct
10 Correct 6948 ms 144212 KB Output is correct
11 Correct 2559 ms 133668 KB Output is correct
12 Correct 4540 ms 133860 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3211 ms 95388 KB Output is correct
2 Correct 3029 ms 91380 KB Output is correct
3 Correct 3087 ms 95376 KB Output is correct
4 Correct 3312 ms 95608 KB Output is correct
5 Correct 3132 ms 94280 KB Output is correct
6 Correct 40 ms 90716 KB Output is correct
7 Correct 9692 ms 119744 KB Output is correct
8 Correct 9925 ms 119756 KB Output is correct
9 Correct 3056 ms 95584 KB Output is correct
10 Correct 8103 ms 117984 KB Output is correct
11 Correct 6692 ms 117424 KB Output is correct
12 Correct 7065 ms 114956 KB Output is correct
13 Correct 9473 ms 113240 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3211 ms 95388 KB Output is correct
2 Correct 3029 ms 91380 KB Output is correct
3 Correct 3087 ms 95376 KB Output is correct
4 Correct 3312 ms 95608 KB Output is correct
5 Correct 3132 ms 94280 KB Output is correct
6 Correct 40 ms 90716 KB Output is correct
7 Execution timed out 10067 ms 133496 KB Time limit exceeded
8 Halted 0 ms 0 KB -