oj.uz

Submission #1025277

# Submission time Handle Problem Language Result Execution time Memory
1025277 2024-07-16T19:06:50 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145360 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<<1),l,((l + r) >> 1)
#define right ((h<<1)|1),((l + r)>>1) + 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 + 5;
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;
pli res;

void upd(bool i,int h,int l,int r){
  if (l == r){
    if (!z) st[i][l].erase(st[i][l].find(oldval));
    st[i][l].insert(newval);
    t[i][h] = {*--st[i][l].end(),l};
    return;
  }
 
  if (idx > (l + r)/2) upd(i,right);
  else upd(i,left);
  t[i][h] = max(t[i][h*2],t[i][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(bool i,int h,int l,int r){
  if (r < L || R < l) return {-inf,0};
  if (L <= l && r <= R) return t[i][h];
  return max(get(i,left),get(i,right));
}
 
int count(ll w,bool zz){
 
  build(1,1,n);
  int tot = 0;
 
  for (int 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];
      res = get(0,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;
      upd(0,1,1,n);
    }
 
    v2 = x[id] - y[id];
    while (tot <= k){
      L = yy[id] + 1; R = n;
      res = get(1,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;
      upd(1,1,1,n);
    }
    
 
    for (int j = roll.size() - 1; j >= 0; j--){
      oldval = roll[j].s.s;
      newval = roll[j].s.f;
      idx = roll[j].f.s;
      z = 0;
      upd(roll[j].f.f,1,1,n);
    }

    oldval = -inf;
    newval = v1;
    idx = yy[id];
    z = 1;
    upd(0,1,1,n);

    newval = v2;
    upd(1,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 2338 ms 95400 KB Output is correct
2 Correct 2393 ms 95356 KB Output is correct
3 Correct 2349 ms 95444 KB Output is correct
4 Correct 2433 ms 95616 KB Output is correct
5 Correct 2314 ms 94396 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6875 ms 137428 KB Output is correct
2 Correct 6667 ms 136848 KB Output is correct
3 Correct 2304 ms 95420 KB Output is correct
4 Correct 6952 ms 136784 KB Output is correct
5 Correct 6562 ms 136844 KB Output is correct
6 Correct 6221 ms 136912 KB Output is correct
7 Correct 5846 ms 136596 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4961 ms 145360 KB Output is correct
2 Correct 5081 ms 145332 KB Output is correct
3 Correct 13 ms 90712 KB Output is correct
4 Correct 1648 ms 133836 KB Output is correct
5 Correct 3381 ms 133836 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4961 ms 145360 KB Output is correct
2 Correct 5081 ms 145332 KB Output is correct
3 Correct 13 ms 90712 KB Output is correct
4 Correct 1648 ms 133836 KB Output is correct
5 Correct 3381 ms 133836 KB Output is correct
6 Correct 5590 ms 145356 KB Output is correct
7 Correct 5701 ms 145356 KB Output is correct
8 Correct 14 ms 90716 KB Output is correct
9 Correct 17 ms 90568 KB Output is correct
10 Correct 5608 ms 143996 KB Output is correct
11 Correct 1689 ms 133832 KB Output is correct
12 Correct 3531 ms 133864 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2338 ms 95400 KB Output is correct
2 Correct 2393 ms 95356 KB Output is correct
3 Correct 2349 ms 95444 KB Output is correct
4 Correct 2433 ms 95616 KB Output is correct
5 Correct 2314 ms 94396 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct
7 Correct 6808 ms 119740 KB Output is correct
8 Correct 6923 ms 119752 KB Output is correct
9 Correct 2462 ms 95620 KB Output is correct
10 Correct 5326 ms 117972 KB Output is correct
11 Correct 4511 ms 117580 KB Output is correct
12 Correct 5020 ms 114888 KB Output is correct
13 Correct 6716 ms 113616 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2338 ms 95400 KB Output is correct
2 Correct 2393 ms 95356 KB Output is correct
3 Correct 2349 ms 95444 KB Output is correct
4 Correct 2433 ms 95616 KB Output is correct
5 Correct 2314 ms 94396 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct
7 Correct 6875 ms 137428 KB Output is correct
8 Correct 6667 ms 136848 KB Output is correct
9 Correct 2304 ms 95420 KB Output is correct
10 Correct 6952 ms 136784 KB Output is correct
11 Correct 6562 ms 136844 KB Output is correct
12 Correct 6221 ms 136912 KB Output is correct
13 Correct 5846 ms 136596 KB Output is correct
14 Correct 4961 ms 145360 KB Output is correct
15 Correct 5081 ms 145332 KB Output is correct
16 Correct 13 ms 90712 KB Output is correct
17 Correct 1648 ms 133836 KB Output is correct
18 Correct 3381 ms 133836 KB Output is correct
19 Correct 5590 ms 145356 KB Output is correct
20 Correct 5701 ms 145356 KB Output is correct
21 Correct 14 ms 90716 KB Output is correct
22 Correct 17 ms 90568 KB Output is correct
23 Correct 5608 ms 143996 KB Output is correct
24 Correct 1689 ms 133832 KB Output is correct
25 Correct 3531 ms 133864 KB Output is correct
26 Correct 6808 ms 119740 KB Output is correct
27 Correct 6923 ms 119752 KB Output is correct
28 Correct 2462 ms 95620 KB Output is correct
29 Correct 5326 ms 117972 KB Output is correct
30 Correct 4511 ms 117580 KB Output is correct
31 Correct 5020 ms 114888 KB Output is correct
32 Correct 6716 ms 113616 KB Output is correct
33 Execution timed out 10023 ms 145356 KB Time limit exceeded
34 Halted 0 ms 0 KB -