oj.uz

Submission #1025262

# Submission time Handle Problem Language Result Execution time Memory
1025262 2024-07-16T18:44:38 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 233928 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;
    int 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);
    }
 
    int 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--){
      upd(roll[j].f.f,1,1,n,roll[j].f.s,roll[j].s.s,roll[j].s.f,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:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2372 ms 181516 KB Output is correct
2 Correct 2269 ms 181712 KB Output is correct
3 Correct 2278 ms 181712 KB Output is correct
4 Correct 2405 ms 181784 KB Output is correct
5 Correct 2409 ms 180416 KB Output is correct
6 Correct 48 ms 176924 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6865 ms 225164 KB Output is correct
2 Correct 6861 ms 225224 KB Output is correct
3 Correct 2284 ms 181432 KB Output is correct
4 Correct 7146 ms 225108 KB Output is correct
5 Correct 6884 ms 225088 KB Output is correct
6 Correct 6689 ms 225136 KB Output is correct
7 Correct 6319 ms 224868 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5005 ms 233812 KB Output is correct
2 Correct 5037 ms 233812 KB Output is correct
3 Correct 26 ms 176724 KB Output is correct
4 Correct 1844 ms 221888 KB Output is correct
5 Correct 3544 ms 222096 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5005 ms 233812 KB Output is correct
2 Correct 5037 ms 233812 KB Output is correct
3 Correct 26 ms 176724 KB Output is correct
4 Correct 1844 ms 221888 KB Output is correct
5 Correct 3544 ms 222096 KB Output is correct
6 Correct 5213 ms 233680 KB Output is correct
7 Correct 5027 ms 233928 KB Output is correct
8 Correct 24 ms 176728 KB Output is correct
9 Correct 26 ms 176728 KB Output is correct
10 Correct 5215 ms 232456 KB Output is correct
11 Correct 1683 ms 221900 KB Output is correct
12 Correct 3516 ms 222100 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2372 ms 181516 KB Output is correct
2 Correct 2269 ms 181712 KB Output is correct
3 Correct 2278 ms 181712 KB Output is correct
4 Correct 2405 ms 181784 KB Output is correct
5 Correct 2409 ms 180416 KB Output is correct
6 Correct 48 ms 176924 KB Output is correct
7 Correct 6545 ms 205908 KB Output is correct
8 Correct 6877 ms 206020 KB Output is correct
9 Correct 2368 ms 181696 KB Output is correct
10 Correct 5294 ms 204292 KB Output is correct
11 Correct 4805 ms 201804 KB Output is correct
12 Correct 5663 ms 199196 KB Output is correct
13 Correct 6917 ms 197776 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2372 ms 181516 KB Output is correct
2 Correct 2269 ms 181712 KB Output is correct
3 Correct 2278 ms 181712 KB Output is correct
4 Correct 2405 ms 181784 KB Output is correct
5 Correct 2409 ms 180416 KB Output is correct
6 Correct 48 ms 176924 KB Output is correct
7 Correct 6865 ms 225164 KB Output is correct
8 Correct 6861 ms 225224 KB Output is correct
9 Correct 2284 ms 181432 KB Output is correct
10 Correct 7146 ms 225108 KB Output is correct
11 Correct 6884 ms 225088 KB Output is correct
12 Correct 6689 ms 225136 KB Output is correct
13 Correct 6319 ms 224868 KB Output is correct
14 Correct 5005 ms 233812 KB Output is correct
15 Correct 5037 ms 233812 KB Output is correct
16 Correct 26 ms 176724 KB Output is correct
17 Correct 1844 ms 221888 KB Output is correct
18 Correct 3544 ms 222096 KB Output is correct
19 Correct 5213 ms 233680 KB Output is correct
20 Correct 5027 ms 233928 KB Output is correct
21 Correct 24 ms 176728 KB Output is correct
22 Correct 26 ms 176728 KB Output is correct
23 Correct 5215 ms 232456 KB Output is correct
24 Correct 1683 ms 221900 KB Output is correct
25 Correct 3516 ms 222100 KB Output is correct
26 Correct 6545 ms 205908 KB Output is correct
27 Correct 6877 ms 206020 KB Output is correct
28 Correct 2368 ms 181696 KB Output is correct
29 Correct 5294 ms 204292 KB Output is correct
30 Correct 4805 ms 201804 KB Output is correct
31 Correct 5663 ms 199196 KB Output is correct
32 Correct 6917 ms 197776 KB Output is correct
33 Execution timed out 10067 ms 227336 KB Time limit exceeded
34 Halted 0 ms 0 KB -