oj.uz

Submission #1025252

# Submission time Handle Problem Language Result Execution time Memory
1025252 2024-07-16T18:23:29 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 231860 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
#define pll pair <ll,ll>
using namespace std;
 
const int N = 3e5 + 5;
const ll inf = 1e18;
pll t[4][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);
}
 
pll get(int i,int h,int l,int r,int L,int R){
  if (r < L || R < l) return {-inf,0LL};
  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){
      pll 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){
      pll 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]];
 
  for (int i = 1; i<= n; 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
  
    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 (ll x: answ)
    cout<<x<<endl;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181764 KB Output is correct
2 Correct 2381 ms 181716 KB Output is correct
3 Correct 2327 ms 181704 KB Output is correct
4 Correct 2496 ms 181788 KB Output is correct
5 Correct 2462 ms 180416 KB Output is correct
6 Correct 48 ms 176980 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8087 ms 225228 KB Output is correct
2 Correct 8362 ms 225160 KB Output is correct
3 Correct 2738 ms 181504 KB Output is correct
4 Correct 8084 ms 225120 KB Output is correct
5 Correct 8449 ms 225136 KB Output is correct
6 Correct 8064 ms 223192 KB Output is correct
7 Correct 7603 ms 222936 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6107 ms 231684 KB Output is correct
2 Correct 5916 ms 231688 KB Output is correct
3 Correct 26 ms 176732 KB Output is correct
4 Correct 2321 ms 219948 KB Output is correct
5 Correct 4465 ms 220152 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6107 ms 231684 KB Output is correct
2 Correct 5916 ms 231688 KB Output is correct
3 Correct 26 ms 176732 KB Output is correct
4 Correct 2321 ms 219948 KB Output is correct
5 Correct 4465 ms 220152 KB Output is correct
6 Correct 7321 ms 231680 KB Output is correct
7 Correct 6989 ms 231860 KB Output is correct
8 Correct 35 ms 176724 KB Output is correct
9 Correct 30 ms 176728 KB Output is correct
10 Correct 7417 ms 230096 KB Output is correct
11 Correct 2138 ms 219860 KB Output is correct
12 Correct 4748 ms 217992 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181764 KB Output is correct
2 Correct 2381 ms 181716 KB Output is correct
3 Correct 2327 ms 181704 KB Output is correct
4 Correct 2496 ms 181788 KB Output is correct
5 Correct 2462 ms 180416 KB Output is correct
6 Correct 48 ms 176980 KB Output is correct
7 Correct 9079 ms 203544 KB Output is correct
8 Correct 8582 ms 203792 KB Output is correct
9 Correct 2904 ms 181780 KB Output is correct
10 Correct 7364 ms 196604 KB Output is correct
11 Correct 6577 ms 196304 KB Output is correct
12 Correct 6497 ms 193616 KB Output is correct
13 Correct 8638 ms 192280 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 181764 KB Output is correct
2 Correct 2381 ms 181716 KB Output is correct
3 Correct 2327 ms 181704 KB Output is correct
4 Correct 2496 ms 181788 KB Output is correct
5 Correct 2462 ms 180416 KB Output is correct
6 Correct 48 ms 176980 KB Output is correct
7 Correct 8087 ms 225228 KB Output is correct
8 Correct 8362 ms 225160 KB Output is correct
9 Correct 2738 ms 181504 KB Output is correct
10 Correct 8084 ms 225120 KB Output is correct
11 Correct 8449 ms 225136 KB Output is correct
12 Correct 8064 ms 223192 KB Output is correct
13 Correct 7603 ms 222936 KB Output is correct
14 Correct 6107 ms 231684 KB Output is correct
15 Correct 5916 ms 231688 KB Output is correct
16 Correct 26 ms 176732 KB Output is correct
17 Correct 2321 ms 219948 KB Output is correct
18 Correct 4465 ms 220152 KB Output is correct
19 Correct 7321 ms 231680 KB Output is correct
20 Correct 6989 ms 231860 KB Output is correct
21 Correct 35 ms 176724 KB Output is correct
22 Correct 30 ms 176728 KB Output is correct
23 Correct 7417 ms 230096 KB Output is correct
24 Correct 2138 ms 219860 KB Output is correct
25 Correct 4748 ms 217992 KB Output is correct
26 Correct 9079 ms 203544 KB Output is correct
27 Correct 8582 ms 203792 KB Output is correct
28 Correct 2904 ms 181780 KB Output is correct
29 Correct 7364 ms 196604 KB Output is correct
30 Correct 6577 ms 196304 KB Output is correct
31 Correct 6497 ms 193616 KB Output is correct
32 Correct 8638 ms 192280 KB Output is correct
33 Execution timed out 10025 ms 227112 KB Time limit exceeded
34 Halted 0 ms 0 KB -