oj.uz

Submission #1025236

# Submission time Handle Problem Language Result Execution time Memory
1025236 2024-07-16T18:08:35 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 299120 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 optimize("Ofast")
#define int ll
using namespace std;
 
const int N = 3e5 + 5,inf = 1e18;
pii t[4][4*N];
int x[N],y[N],yy[N],n,k;
multiset <int> st[4][4*N];
pii arr[N];
vector <int> answ;
 
void upd(int i,int h,int l,int r,int idx,int oldval,int 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);
}
 
pii 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(int 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,pii> > roll;
 
    int id = arr[i].s,v1 = x[id] + y[id];
    while (tot <= k){
      pii res = get(1,1,1,n,1,yy[id]);
      int 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){
      pii res = get(2,1,1,n,yy[id] + 1,n);
      int 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,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]];
 
  for (int i = 1; i<= n; i++)
    arr[i] = {x[i],i};
  sort(arr+1,arr+n+1);
 
  int l = 0,r = 4e9,res = -1;
  while (l <= r){
    int mid = (l + r) >> 1;
    //umciresi w iseti rom w ze naklebi an toli wonis wiboebis raodenoba >= k ze
  
    int c = count(mid,0);
    if (c >= 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 (int x: answ)
    cout<<x<<endl;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:108:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2576 ms 237100 KB Output is correct
2 Correct 2651 ms 235072 KB Output is correct
3 Correct 2520 ms 237256 KB Output is correct
4 Correct 2741 ms 237208 KB Output is correct
5 Correct 2678 ms 233996 KB Output is correct
6 Correct 59 ms 228436 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9420 ms 282980 KB Output is correct
2 Correct 9151 ms 285192 KB Output is correct
3 Correct 2875 ms 231040 KB Output is correct
4 Correct 9097 ms 284040 KB Output is correct
5 Correct 8364 ms 285380 KB Output is correct
6 Correct 7564 ms 285632 KB Output is correct
7 Correct 7591 ms 285124 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5906 ms 296612 KB Output is correct
2 Correct 6134 ms 298948 KB Output is correct
3 Correct 37 ms 230232 KB Output is correct
4 Correct 2339 ms 281036 KB Output is correct
5 Correct 4122 ms 283624 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5906 ms 296612 KB Output is correct
2 Correct 6134 ms 298948 KB Output is correct
3 Correct 37 ms 230232 KB Output is correct
4 Correct 2339 ms 281036 KB Output is correct
5 Correct 4122 ms 283624 KB Output is correct
6 Correct 6715 ms 299120 KB Output is correct
7 Correct 6451 ms 299116 KB Output is correct
8 Correct 36 ms 230228 KB Output is correct
9 Correct 38 ms 230232 KB Output is correct
10 Correct 6286 ms 297060 KB Output is correct
11 Correct 1988 ms 281272 KB Output is correct
12 Correct 4298 ms 283592 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2576 ms 237100 KB Output is correct
2 Correct 2651 ms 235072 KB Output is correct
3 Correct 2520 ms 237256 KB Output is correct
4 Correct 2741 ms 237208 KB Output is correct
5 Correct 2678 ms 233996 KB Output is correct
6 Correct 59 ms 228436 KB Output is correct
7 Correct 7641 ms 263960 KB Output is correct
8 Correct 7548 ms 263932 KB Output is correct
9 Correct 2506 ms 235032 KB Output is correct
10 Correct 5917 ms 261412 KB Output is correct
11 Correct 5057 ms 260628 KB Output is correct
12 Correct 5497 ms 257100 KB Output is correct
13 Correct 7045 ms 256264 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2576 ms 237100 KB Output is correct
2 Correct 2651 ms 235072 KB Output is correct
3 Correct 2520 ms 237256 KB Output is correct
4 Correct 2741 ms 237208 KB Output is correct
5 Correct 2678 ms 233996 KB Output is correct
6 Correct 59 ms 228436 KB Output is correct
7 Correct 9420 ms 282980 KB Output is correct
8 Correct 9151 ms 285192 KB Output is correct
9 Correct 2875 ms 231040 KB Output is correct
10 Correct 9097 ms 284040 KB Output is correct
11 Correct 8364 ms 285380 KB Output is correct
12 Correct 7564 ms 285632 KB Output is correct
13 Correct 7591 ms 285124 KB Output is correct
14 Correct 5906 ms 296612 KB Output is correct
15 Correct 6134 ms 298948 KB Output is correct
16 Correct 37 ms 230232 KB Output is correct
17 Correct 2339 ms 281036 KB Output is correct
18 Correct 4122 ms 283624 KB Output is correct
19 Correct 6715 ms 299120 KB Output is correct
20 Correct 6451 ms 299116 KB Output is correct
21 Correct 36 ms 230228 KB Output is correct
22 Correct 38 ms 230232 KB Output is correct
23 Correct 6286 ms 297060 KB Output is correct
24 Correct 1988 ms 281272 KB Output is correct
25 Correct 4298 ms 283592 KB Output is correct
26 Correct 7641 ms 263960 KB Output is correct
27 Correct 7548 ms 263932 KB Output is correct
28 Correct 2506 ms 235032 KB Output is correct
29 Correct 5917 ms 261412 KB Output is correct
30 Correct 5057 ms 260628 KB Output is correct
31 Correct 5497 ms 257100 KB Output is correct
32 Correct 7045 ms 256264 KB Output is correct
33 Execution timed out 10042 ms 298884 KB Time limit exceeded
34 Halted 0 ms 0 KB -