oj.uz

Submission #1025259

# Submission time Handle Problem Language Result Execution time Memory
1025259 2024-07-16T18:38:34 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 233740 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[3][3*N];
int x[N],y[N],yy[N],n,k;
multiset <ll> st[4][3*N];
pii arr[N];
vector <ll> answ;
 
void upd(int i,int h,int l,int r,int idx,ll oldval,ll newval,bool z){
  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,idx, oldval, newval,z);
  else upd(i,left,idx, oldval, newval,z);
  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[2][h] = {-inf,0};
  if (l == r) {
    st[1][l].clear();
    st[2][l].clear();
    return;
  }
  build(left);
  build(right);
}
 
pli get(int i,int h,int l,int r,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,L,R),get(i,right,L,R));
}
 
int count(ll w,bool z){
 
  build(1,1,n);
  int tot = 0;
  for (int i = 1; i <= n; i++){
    if (tot > k) return tot;
    vector <pair <pii,pll> > roll;
 
    int id = arr[i].s;
    ll v1 = x[id] + y[id];
    while (tot <= k){
      pli res = get(1,1,1,n,1,yy[id]);
      ll w1 = v1 - res.f;
      if (w1 > w) break;
      if (z) answ.pb(w1);
 
      tot += 1;
      roll.pb({{1,res.s},{res.f,-inf}});
      upd(1,1,1,n,res.s,res.f, -inf,0);
    }
 
    ll v2 = x[id] - y[id];
    while (tot <= k){
      pli res = get(2,1,1,n,yy[id] + 1,n);
      ll w1 = v2 - res.f;
      if (w1 > w) break;
      if (z) answ.pb(w1);
 
      tot += 1;
      roll.pb({{2,res.s},{res.f,-inf}});
      upd(2,1,1,n,res.s,res.f, -inf,0);
    }
 
    for (int j = roll.size() - 1; j >= 0; j--){
      int ii = roll[j].f.f,idx = roll[j].f.s;
      ll oldval = roll[j].s.s,newval = roll[j].s.f;
      upd(ii,1,1,n,idx,oldval,newval,0);
    }
 
    upd(1,1,1,n,yy[id],-inf,v1,1);
    upd(2,1,1,n,yy[id],-inf,v2,1);
  }
 
  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:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181576 KB Output is correct
2 Correct 2462 ms 181536 KB Output is correct
3 Correct 2167 ms 181552 KB Output is correct
4 Correct 2314 ms 181788 KB Output is correct
5 Correct 2394 ms 180412 KB Output is correct
6 Correct 48 ms 176984 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7086 ms 223132 KB Output is correct
2 Correct 7389 ms 223040 KB Output is correct
3 Correct 2472 ms 181436 KB Output is correct
4 Correct 6843 ms 222836 KB Output is correct
5 Correct 7183 ms 223016 KB Output is correct
6 Correct 6562 ms 223108 KB Output is correct
7 Correct 6567 ms 222664 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6287 ms 231684 KB Output is correct
2 Correct 5124 ms 231532 KB Output is correct
3 Correct 24 ms 176732 KB Output is correct
4 Correct 1739 ms 219860 KB Output is correct
5 Correct 3207 ms 219856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6287 ms 231684 KB Output is correct
2 Correct 5124 ms 231532 KB Output is correct
3 Correct 24 ms 176732 KB Output is correct
4 Correct 1739 ms 219860 KB Output is correct
5 Correct 3207 ms 219856 KB Output is correct
6 Correct 5294 ms 231684 KB Output is correct
7 Correct 5363 ms 231680 KB Output is correct
8 Correct 25 ms 176720 KB Output is correct
9 Correct 24 ms 176732 KB Output is correct
10 Correct 5271 ms 230092 KB Output is correct
11 Correct 1503 ms 219848 KB Output is correct
12 Correct 3300 ms 219972 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181576 KB Output is correct
2 Correct 2462 ms 181536 KB Output is correct
3 Correct 2167 ms 181552 KB Output is correct
4 Correct 2314 ms 181788 KB Output is correct
5 Correct 2394 ms 180412 KB Output is correct
6 Correct 48 ms 176984 KB Output is correct
7 Correct 5849 ms 203676 KB Output is correct
8 Correct 6303 ms 205856 KB Output is correct
9 Correct 2228 ms 181696 KB Output is correct
10 Correct 4874 ms 204120 KB Output is correct
11 Correct 3910 ms 203584 KB Output is correct
12 Correct 4526 ms 201172 KB Output is correct
13 Correct 6075 ms 199968 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181576 KB Output is correct
2 Correct 2462 ms 181536 KB Output is correct
3 Correct 2167 ms 181552 KB Output is correct
4 Correct 2314 ms 181788 KB Output is correct
5 Correct 2394 ms 180412 KB Output is correct
6 Correct 48 ms 176984 KB Output is correct
7 Correct 7086 ms 223132 KB Output is correct
8 Correct 7389 ms 223040 KB Output is correct
9 Correct 2472 ms 181436 KB Output is correct
10 Correct 6843 ms 222836 KB Output is correct
11 Correct 7183 ms 223016 KB Output is correct
12 Correct 6562 ms 223108 KB Output is correct
13 Correct 6567 ms 222664 KB Output is correct
14 Correct 6287 ms 231684 KB Output is correct
15 Correct 5124 ms 231532 KB Output is correct
16 Correct 24 ms 176732 KB Output is correct
17 Correct 1739 ms 219860 KB Output is correct
18 Correct 3207 ms 219856 KB Output is correct
19 Correct 5294 ms 231684 KB Output is correct
20 Correct 5363 ms 231680 KB Output is correct
21 Correct 25 ms 176720 KB Output is correct
22 Correct 24 ms 176732 KB Output is correct
23 Correct 5271 ms 230092 KB Output is correct
24 Correct 1503 ms 219848 KB Output is correct
25 Correct 3300 ms 219972 KB Output is correct
26 Correct 5849 ms 203676 KB Output is correct
27 Correct 6303 ms 205856 KB Output is correct
28 Correct 2228 ms 181696 KB Output is correct
29 Correct 4874 ms 204120 KB Output is correct
30 Correct 3910 ms 203584 KB Output is correct
31 Correct 4526 ms 201172 KB Output is correct
32 Correct 6075 ms 199968 KB Output is correct
33 Execution timed out 10017 ms 233740 KB Time limit exceeded
34 Halted 0 ms 0 KB -