oj.uz

Submission #1025238

# Submission time Handle Problem Language Result Execution time Memory
1025238 2024-07-16T18:11:53 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 299464 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 2414 ms 239036 KB Output is correct
2 Correct 2369 ms 239296 KB Output is correct
3 Correct 2325 ms 239248 KB Output is correct
4 Correct 2422 ms 239304 KB Output is correct
5 Correct 2368 ms 238276 KB Output is correct
6 Correct 52 ms 236372 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7635 ms 287900 KB Output is correct
2 Correct 7789 ms 287188 KB Output is correct
3 Correct 2593 ms 238972 KB Output is correct
4 Correct 8462 ms 286192 KB Output is correct
5 Correct 7462 ms 287684 KB Output is correct
6 Correct 6936 ms 287236 KB Output is correct
7 Correct 7114 ms 286768 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6116 ms 299464 KB Output is correct
2 Correct 6863 ms 295828 KB Output is correct
3 Correct 39 ms 234324 KB Output is correct
4 Correct 2041 ms 280172 KB Output is correct
5 Correct 4066 ms 280260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6116 ms 299464 KB Output is correct
2 Correct 6863 ms 295828 KB Output is correct
3 Correct 39 ms 234324 KB Output is correct
4 Correct 2041 ms 280172 KB Output is correct
5 Correct 4066 ms 280260 KB Output is correct
6 Correct 6485 ms 295776 KB Output is correct
7 Correct 7129 ms 295824 KB Output is correct
8 Correct 34 ms 236188 KB Output is correct
9 Correct 33 ms 234324 KB Output is correct
10 Correct 6446 ms 293828 KB Output is correct
11 Correct 1731 ms 280008 KB Output is correct
12 Correct 4090 ms 280204 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2414 ms 239036 KB Output is correct
2 Correct 2369 ms 239296 KB Output is correct
3 Correct 2325 ms 239248 KB Output is correct
4 Correct 2422 ms 239304 KB Output is correct
5 Correct 2368 ms 238276 KB Output is correct
6 Correct 52 ms 236372 KB Output is correct
7 Correct 6640 ms 263752 KB Output is correct
8 Correct 7666 ms 263812 KB Output is correct
9 Correct 2253 ms 241080 KB Output is correct
10 Correct 5828 ms 256944 KB Output is correct
11 Correct 5261 ms 256420 KB Output is correct
12 Correct 5654 ms 252660 KB Output is correct
13 Correct 7586 ms 251852 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2414 ms 239036 KB Output is correct
2 Correct 2369 ms 239296 KB Output is correct
3 Correct 2325 ms 239248 KB Output is correct
4 Correct 2422 ms 239304 KB Output is correct
5 Correct 2368 ms 238276 KB Output is correct
6 Correct 52 ms 236372 KB Output is correct
7 Correct 7635 ms 287900 KB Output is correct
8 Correct 7789 ms 287188 KB Output is correct
9 Correct 2593 ms 238972 KB Output is correct
10 Correct 8462 ms 286192 KB Output is correct
11 Correct 7462 ms 287684 KB Output is correct
12 Correct 6936 ms 287236 KB Output is correct
13 Correct 7114 ms 286768 KB Output is correct
14 Correct 6116 ms 299464 KB Output is correct
15 Correct 6863 ms 295828 KB Output is correct
16 Correct 39 ms 234324 KB Output is correct
17 Correct 2041 ms 280172 KB Output is correct
18 Correct 4066 ms 280260 KB Output is correct
19 Correct 6485 ms 295776 KB Output is correct
20 Correct 7129 ms 295824 KB Output is correct
21 Correct 34 ms 236188 KB Output is correct
22 Correct 33 ms 234324 KB Output is correct
23 Correct 6446 ms 293828 KB Output is correct
24 Correct 1731 ms 280008 KB Output is correct
25 Correct 4090 ms 280204 KB Output is correct
26 Correct 6640 ms 263752 KB Output is correct
27 Correct 7666 ms 263812 KB Output is correct
28 Correct 2253 ms 241080 KB Output is correct
29 Correct 5828 ms 256944 KB Output is correct
30 Correct 5261 ms 256420 KB Output is correct
31 Correct 5654 ms 252660 KB Output is correct
32 Correct 7586 ms 251852 KB Output is correct
33 Execution timed out 10110 ms 293576 KB Time limit exceeded
34 Halted 0 ms 0 KB -