oj.uz

Submission #1025273

# Submission time Handle Problem Language Result Execution time Memory
1025273 2024-07-16T19:00:04 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145588 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;
      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;
      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:133:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2772 ms 95404 KB Output is correct
2 Correct 2714 ms 95396 KB Output is correct
3 Correct 2672 ms 95372 KB Output is correct
4 Correct 2593 ms 95444 KB Output is correct
5 Correct 2710 ms 94200 KB Output is correct
6 Correct 43 ms 90716 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7489 ms 137128 KB Output is correct
2 Correct 6545 ms 136908 KB Output is correct
3 Correct 2255 ms 95316 KB Output is correct
4 Correct 7190 ms 136784 KB Output is correct
5 Correct 7939 ms 136932 KB Output is correct
6 Correct 7827 ms 136904 KB Output is correct
7 Correct 7322 ms 136648 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6373 ms 145360 KB Output is correct
2 Correct 6109 ms 145356 KB Output is correct
3 Correct 17 ms 90752 KB Output is correct
4 Correct 1954 ms 133836 KB Output is correct
5 Correct 4326 ms 133324 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6373 ms 145360 KB Output is correct
2 Correct 6109 ms 145356 KB Output is correct
3 Correct 17 ms 90752 KB Output is correct
4 Correct 1954 ms 133836 KB Output is correct
5 Correct 4326 ms 133324 KB Output is correct
6 Correct 6750 ms 145584 KB Output is correct
7 Correct 6467 ms 145276 KB Output is correct
8 Correct 17 ms 90712 KB Output is correct
9 Correct 12 ms 90528 KB Output is correct
10 Correct 6419 ms 143880 KB Output is correct
11 Correct 2033 ms 133324 KB Output is correct
12 Correct 4097 ms 133552 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2772 ms 95404 KB Output is correct
2 Correct 2714 ms 95396 KB Output is correct
3 Correct 2672 ms 95372 KB Output is correct
4 Correct 2593 ms 95444 KB Output is correct
5 Correct 2710 ms 94200 KB Output is correct
6 Correct 43 ms 90716 KB Output is correct
7 Correct 8421 ms 119396 KB Output is correct
8 Correct 8548 ms 116168 KB Output is correct
9 Correct 2766 ms 95616 KB Output is correct
10 Correct 6359 ms 117976 KB Output is correct
11 Correct 5542 ms 117568 KB Output is correct
12 Correct 5397 ms 114964 KB Output is correct
13 Correct 6677 ms 113540 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2772 ms 95404 KB Output is correct
2 Correct 2714 ms 95396 KB Output is correct
3 Correct 2672 ms 95372 KB Output is correct
4 Correct 2593 ms 95444 KB Output is correct
5 Correct 2710 ms 94200 KB Output is correct
6 Correct 43 ms 90716 KB Output is correct
7 Correct 7489 ms 137128 KB Output is correct
8 Correct 6545 ms 136908 KB Output is correct
9 Correct 2255 ms 95316 KB Output is correct
10 Correct 7190 ms 136784 KB Output is correct
11 Correct 7939 ms 136932 KB Output is correct
12 Correct 7827 ms 136904 KB Output is correct
13 Correct 7322 ms 136648 KB Output is correct
14 Correct 6373 ms 145360 KB Output is correct
15 Correct 6109 ms 145356 KB Output is correct
16 Correct 17 ms 90752 KB Output is correct
17 Correct 1954 ms 133836 KB Output is correct
18 Correct 4326 ms 133324 KB Output is correct
19 Correct 6750 ms 145584 KB Output is correct
20 Correct 6467 ms 145276 KB Output is correct
21 Correct 17 ms 90712 KB Output is correct
22 Correct 12 ms 90528 KB Output is correct
23 Correct 6419 ms 143880 KB Output is correct
24 Correct 2033 ms 133324 KB Output is correct
25 Correct 4097 ms 133552 KB Output is correct
26 Correct 8421 ms 119396 KB Output is correct
27 Correct 8548 ms 116168 KB Output is correct
28 Correct 2766 ms 95616 KB Output is correct
29 Correct 6359 ms 117976 KB Output is correct
30 Correct 5542 ms 117568 KB Output is correct
31 Correct 5397 ms 114964 KB Output is correct
32 Correct 6677 ms 113540 KB Output is correct
33 Execution timed out 10033 ms 145588 KB Time limit exceeded
34 Halted 0 ms 0 KB -