oj.uz

Submission #1025241

# Submission time Handle Problem Language Result Execution time Memory
1025241 2024-07-16T18:13:54 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 241732 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")
#define int ll
using namespace std;
 
const int N = 3e5 + 5,inf = 1e18;
pii t[4][3*N];
int x[N],y[N],yy[N],n,k;
multiset <int> st[4][3*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 2461 ms 174268 KB Output is correct
2 Correct 2448 ms 174408 KB Output is correct
3 Correct 2308 ms 183240 KB Output is correct
4 Correct 2386 ms 174808 KB Output is correct
5 Correct 2364 ms 173760 KB Output is correct
6 Correct 78 ms 170068 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8173 ms 226236 KB Output is correct
2 Correct 8729 ms 225732 KB Output is correct
3 Correct 2764 ms 174532 KB Output is correct
4 Correct 9482 ms 224640 KB Output is correct
5 Correct 8377 ms 231756 KB Output is correct
6 Correct 8193 ms 227324 KB Output is correct
7 Correct 7622 ms 230992 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7394 ms 241720 KB Output is correct
2 Correct 7333 ms 238364 KB Output is correct
3 Correct 35 ms 169776 KB Output is correct
4 Correct 2675 ms 221584 KB Output is correct
5 Correct 5061 ms 221668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7394 ms 241720 KB Output is correct
2 Correct 7333 ms 238364 KB Output is correct
3 Correct 35 ms 169776 KB Output is correct
4 Correct 2675 ms 221584 KB Output is correct
5 Correct 5061 ms 221668 KB Output is correct
6 Correct 7693 ms 241728 KB Output is correct
7 Correct 7052 ms 241732 KB Output is correct
8 Correct 29 ms 178780 KB Output is correct
9 Correct 28 ms 178780 KB Output is correct
10 Correct 7382 ms 236560 KB Output is correct
11 Correct 1850 ms 221444 KB Output is correct
12 Correct 3844 ms 227016 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 174268 KB Output is correct
2 Correct 2448 ms 174408 KB Output is correct
3 Correct 2308 ms 183240 KB Output is correct
4 Correct 2386 ms 174808 KB Output is correct
5 Correct 2364 ms 173760 KB Output is correct
6 Correct 78 ms 170068 KB Output is correct
7 Correct 7183 ms 212488 KB Output is correct
8 Correct 7602 ms 212492 KB Output is correct
9 Correct 2378 ms 183764 KB Output is correct
10 Correct 6061 ms 209960 KB Output is correct
11 Correct 5134 ms 199876 KB Output is correct
12 Correct 5746 ms 196208 KB Output is correct
13 Correct 7501 ms 195484 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 174268 KB Output is correct
2 Correct 2448 ms 174408 KB Output is correct
3 Correct 2308 ms 183240 KB Output is correct
4 Correct 2386 ms 174808 KB Output is correct
5 Correct 2364 ms 173760 KB Output is correct
6 Correct 78 ms 170068 KB Output is correct
7 Correct 8173 ms 226236 KB Output is correct
8 Correct 8729 ms 225732 KB Output is correct
9 Correct 2764 ms 174532 KB Output is correct
10 Correct 9482 ms 224640 KB Output is correct
11 Correct 8377 ms 231756 KB Output is correct
12 Correct 8193 ms 227324 KB Output is correct
13 Correct 7622 ms 230992 KB Output is correct
14 Correct 7394 ms 241720 KB Output is correct
15 Correct 7333 ms 238364 KB Output is correct
16 Correct 35 ms 169776 KB Output is correct
17 Correct 2675 ms 221584 KB Output is correct
18 Correct 5061 ms 221668 KB Output is correct
19 Correct 7693 ms 241728 KB Output is correct
20 Correct 7052 ms 241732 KB Output is correct
21 Correct 29 ms 178780 KB Output is correct
22 Correct 28 ms 178780 KB Output is correct
23 Correct 7382 ms 236560 KB Output is correct
24 Correct 1850 ms 221444 KB Output is correct
25 Correct 3844 ms 227016 KB Output is correct
26 Correct 7183 ms 212488 KB Output is correct
27 Correct 7602 ms 212492 KB Output is correct
28 Correct 2378 ms 183764 KB Output is correct
29 Correct 6061 ms 209960 KB Output is correct
30 Correct 5134 ms 199876 KB Output is correct
31 Correct 5746 ms 196208 KB Output is correct
32 Correct 7501 ms 195484 KB Output is correct
33 Execution timed out 10073 ms 237184 KB Time limit exceeded
34 Halted 0 ms 0 KB -