oj.uz

Submission #1025293

# Submission time Handle Problem Language Result Execution time Memory
1025293 2024-07-16T19:21:08 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
59 / 100
 10000 ms 131212 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 = 250003;
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 3470 ms 83084 KB Output is correct
2 Correct 3194 ms 83032 KB Output is correct
3 Correct 2984 ms 83160 KB Output is correct
4 Correct 3130 ms 83304 KB Output is correct
5 Correct 3211 ms 82064 KB Output is correct
6 Correct 48 ms 78428 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6988 ms 131024 KB Output is correct
2 Correct 7146 ms 131212 KB Output is correct
3 Correct 14 ms 78428 KB Output is correct
4 Correct 2766 ms 119476 KB Output is correct
5 Correct 4746 ms 119412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6988 ms 131024 KB Output is correct
2 Correct 7146 ms 131212 KB Output is correct
3 Correct 14 ms 78428 KB Output is correct
4 Correct 2766 ms 119476 KB Output is correct
5 Correct 4746 ms 119412 KB Output is correct
6 Correct 7290 ms 131148 KB Output is correct
7 Correct 7310 ms 131176 KB Output is correct
8 Correct 14 ms 78424 KB Output is correct
9 Correct 14 ms 78344 KB Output is correct
10 Correct 7932 ms 129860 KB Output is correct
11 Correct 2681 ms 119476 KB Output is correct
12 Correct 5234 ms 119500 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3470 ms 83084 KB Output is correct
2 Correct 3194 ms 83032 KB Output is correct
3 Correct 2984 ms 83160 KB Output is correct
4 Correct 3130 ms 83304 KB Output is correct
5 Correct 3211 ms 82064 KB Output is correct
6 Correct 48 ms 78428 KB Output is correct
7 Correct 9231 ms 105380 KB Output is correct
8 Correct 9413 ms 105388 KB Output is correct
9 Correct 3126 ms 83304 KB Output is correct
10 Correct 7932 ms 103612 KB Output is correct
11 Correct 6683 ms 103168 KB Output is correct
12 Correct 7016 ms 100604 KB Output is correct
13 Correct 8260 ms 99132 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3470 ms 83084 KB Output is correct
2 Correct 3194 ms 83032 KB Output is correct
3 Correct 2984 ms 83160 KB Output is correct
4 Correct 3130 ms 83304 KB Output is correct
5 Correct 3211 ms 82064 KB Output is correct
6 Correct 48 ms 78428 KB Output is correct
7 Execution timed out 10022 ms 118004 KB Time limit exceeded
8 Halted 0 ms 0 KB -