oj.uz

Submission #1025258

# Submission time Handle Problem Language Result Execution time Memory
1025258 2024-07-16T18:33:30 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 233836 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 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 2321 ms 181716 KB Output is correct
2 Correct 2538 ms 181712 KB Output is correct
3 Correct 2262 ms 181744 KB Output is correct
4 Correct 2360 ms 181708 KB Output is correct
5 Correct 2316 ms 180548 KB Output is correct
6 Correct 51 ms 176976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7095 ms 225064 KB Output is correct
2 Correct 7101 ms 225160 KB Output is correct
3 Correct 2540 ms 181432 KB Output is correct
4 Correct 7444 ms 225072 KB Output is correct
5 Correct 6966 ms 225176 KB Output is correct
6 Correct 6627 ms 225140 KB Output is correct
7 Correct 6346 ms 224968 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5210 ms 233812 KB Output is correct
2 Correct 5197 ms 233836 KB Output is correct
3 Correct 29 ms 176732 KB Output is correct
4 Correct 1804 ms 221828 KB Output is correct
5 Correct 3664 ms 221900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5210 ms 233812 KB Output is correct
2 Correct 5197 ms 233836 KB Output is correct
3 Correct 29 ms 176732 KB Output is correct
4 Correct 1804 ms 221828 KB Output is correct
5 Correct 3664 ms 221900 KB Output is correct
6 Correct 5738 ms 233636 KB Output is correct
7 Correct 5323 ms 233676 KB Output is correct
8 Correct 28 ms 176720 KB Output is correct
9 Correct 28 ms 176732 KB Output is correct
10 Correct 5449 ms 232452 KB Output is correct
11 Correct 1548 ms 222068 KB Output is correct
12 Correct 3462 ms 222096 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2321 ms 181716 KB Output is correct
2 Correct 2538 ms 181712 KB Output is correct
3 Correct 2262 ms 181744 KB Output is correct
4 Correct 2360 ms 181708 KB Output is correct
5 Correct 2316 ms 180548 KB Output is correct
6 Correct 51 ms 176976 KB Output is correct
7 Correct 6385 ms 205720 KB Output is correct
8 Correct 6193 ms 205920 KB Output is correct
9 Correct 2228 ms 181700 KB Output is correct
10 Correct 5030 ms 204116 KB Output is correct
11 Correct 4381 ms 203596 KB Output is correct
12 Correct 4773 ms 201036 KB Output is correct
13 Correct 6124 ms 199884 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2321 ms 181716 KB Output is correct
2 Correct 2538 ms 181712 KB Output is correct
3 Correct 2262 ms 181744 KB Output is correct
4 Correct 2360 ms 181708 KB Output is correct
5 Correct 2316 ms 180548 KB Output is correct
6 Correct 51 ms 176976 KB Output is correct
7 Correct 7095 ms 225064 KB Output is correct
8 Correct 7101 ms 225160 KB Output is correct
9 Correct 2540 ms 181432 KB Output is correct
10 Correct 7444 ms 225072 KB Output is correct
11 Correct 6966 ms 225176 KB Output is correct
12 Correct 6627 ms 225140 KB Output is correct
13 Correct 6346 ms 224968 KB Output is correct
14 Correct 5210 ms 233812 KB Output is correct
15 Correct 5197 ms 233836 KB Output is correct
16 Correct 29 ms 176732 KB Output is correct
17 Correct 1804 ms 221828 KB Output is correct
18 Correct 3664 ms 221900 KB Output is correct
19 Correct 5738 ms 233636 KB Output is correct
20 Correct 5323 ms 233676 KB Output is correct
21 Correct 28 ms 176720 KB Output is correct
22 Correct 28 ms 176732 KB Output is correct
23 Correct 5449 ms 232452 KB Output is correct
24 Correct 1548 ms 222068 KB Output is correct
25 Correct 3462 ms 222096 KB Output is correct
26 Correct 6385 ms 205720 KB Output is correct
27 Correct 6193 ms 205920 KB Output is correct
28 Correct 2228 ms 181700 KB Output is correct
29 Correct 5030 ms 204116 KB Output is correct
30 Correct 4381 ms 203596 KB Output is correct
31 Correct 4773 ms 201036 KB Output is correct
32 Correct 6124 ms 199884 KB Output is correct
33 Execution timed out 10066 ms 233576 KB Time limit exceeded
34 Halted 0 ms 0 KB -