oj.uz

Submission #1025278

# Submission time Handle Problem Language Result Execution time Memory
1025278 2024-07-16T19:08:11 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145576 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 pli pair <ll,int>
#define pll pair <ll,ll>
using namespace std;
 
const int N = 3e5 + 3;
const ll inf = 1e18;
pli t[2][3*N];
int x[N],y[N],yy[N],n,k,L,R;
multiset <ll> st[2][3*N];
pii arr[N];
vector <ll> answ;
ll oldval,newval,w1;
int idx,v1,v2,id;
bool z;
pli res;
 
void upd(bool i,int h,int l,int r){
  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);
  else upd(i,left);
  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[0][h] = {-inf,0};
  if (l == r) {
    st[1][l].clear();
    st[0][l].clear();
    return;
  }
  build(left);
  build(right);
}
 
pli get(bool i,int h,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),get(i,right));
}
 
int count(ll w,bool zz){
 
  build(1,1,n);
  int tot = 0,i,j;
 
  for (i = 1; i <= n; i++){
    if (tot > k) return tot;
    vector <pair <pii,pll> > roll;
 
    id = arr[i].s; v1 = x[id] + y[id];
    while (tot <= k){
      L = 1; R = yy[id];
      res = get(0,1,1,n);
      w1 = v1 - res.f;
      if (w1 > w) break;
      if (zz) answ.pb(w1);
 
      tot += 1;
      if (tot > k) return tot;
      roll.pb({{0,res.s},{res.f,-inf}});
      idx = res.s; oldval = res.f; newval = -inf;
      z = 0;
      upd(0,1,1,n);
    }
 
    v2 = x[id] - y[id];
    while (tot <= k){
      L = yy[id] + 1; R = n;
      res = get(1,1,1,n);
      w1 = v2 - res.f;
      if (w1 > w) break;
      if (zz) answ.pb(w1);
 
      tot += 1;
      if (tot > k) return tot;
      roll.pb({{1,res.s},{res.f,-inf}});
      oldval = res.f;
      newval = -inf;
      idx = res.s;
      z = 0;
      upd(1,1,1,n);
    }
    
 
    for (j = roll.size() - 1; j >= 0; j--){
      oldval = roll[j].s.s;
      newval = roll[j].s.f;
      idx = roll[j].f.s;
      z = 0;
      upd(roll[j].f.f,1,1,n);
    }
 
    oldval = -inf;
    newval = v1;
    idx = yy[id];
    z = 1;
    upd(0,1,1,n);
 
    newval = v2;
    upd(1,1,1,n);
  }
 
  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]];
    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
  
    if (count(mid,0) >= 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:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2589 ms 95440 KB Output is correct
2 Correct 2529 ms 95440 KB Output is correct
3 Correct 2391 ms 95356 KB Output is correct
4 Correct 2493 ms 95616 KB Output is correct
5 Correct 2464 ms 94400 KB Output is correct
6 Correct 34 ms 90712 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7165 ms 137428 KB Output is correct
2 Correct 7182 ms 136844 KB Output is correct
3 Correct 2437 ms 95324 KB Output is correct
4 Correct 6961 ms 136788 KB Output is correct
5 Correct 6914 ms 137032 KB Output is correct
6 Correct 6894 ms 136900 KB Output is correct
7 Correct 6184 ms 136588 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5663 ms 145576 KB Output is correct
2 Correct 4898 ms 145472 KB Output is correct
3 Correct 12 ms 90716 KB Output is correct
4 Correct 1731 ms 133984 KB Output is correct
5 Correct 3225 ms 133860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5663 ms 145576 KB Output is correct
2 Correct 4898 ms 145472 KB Output is correct
3 Correct 12 ms 90716 KB Output is correct
4 Correct 1731 ms 133984 KB Output is correct
5 Correct 3225 ms 133860 KB Output is correct
6 Correct 5248 ms 145352 KB Output is correct
7 Correct 5175 ms 145536 KB Output is correct
8 Correct 12 ms 90712 KB Output is correct
9 Correct 13 ms 90584 KB Output is correct
10 Correct 5288 ms 144208 KB Output is correct
11 Correct 1429 ms 133744 KB Output is correct
12 Correct 3621 ms 133840 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2589 ms 95440 KB Output is correct
2 Correct 2529 ms 95440 KB Output is correct
3 Correct 2391 ms 95356 KB Output is correct
4 Correct 2493 ms 95616 KB Output is correct
5 Correct 2464 ms 94400 KB Output is correct
6 Correct 34 ms 90712 KB Output is correct
7 Correct 6664 ms 119752 KB Output is correct
8 Correct 6249 ms 119752 KB Output is correct
9 Correct 2255 ms 95592 KB Output is correct
10 Correct 5200 ms 118104 KB Output is correct
11 Correct 4444 ms 117504 KB Output is correct
12 Correct 4605 ms 114968 KB Output is correct
13 Correct 5964 ms 113604 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2589 ms 95440 KB Output is correct
2 Correct 2529 ms 95440 KB Output is correct
3 Correct 2391 ms 95356 KB Output is correct
4 Correct 2493 ms 95616 KB Output is correct
5 Correct 2464 ms 94400 KB Output is correct
6 Correct 34 ms 90712 KB Output is correct
7 Correct 7165 ms 137428 KB Output is correct
8 Correct 7182 ms 136844 KB Output is correct
9 Correct 2437 ms 95324 KB Output is correct
10 Correct 6961 ms 136788 KB Output is correct
11 Correct 6914 ms 137032 KB Output is correct
12 Correct 6894 ms 136900 KB Output is correct
13 Correct 6184 ms 136588 KB Output is correct
14 Correct 5663 ms 145576 KB Output is correct
15 Correct 4898 ms 145472 KB Output is correct
16 Correct 12 ms 90716 KB Output is correct
17 Correct 1731 ms 133984 KB Output is correct
18 Correct 3225 ms 133860 KB Output is correct
19 Correct 5248 ms 145352 KB Output is correct
20 Correct 5175 ms 145536 KB Output is correct
21 Correct 12 ms 90712 KB Output is correct
22 Correct 13 ms 90584 KB Output is correct
23 Correct 5288 ms 144208 KB Output is correct
24 Correct 1429 ms 133744 KB Output is correct
25 Correct 3621 ms 133840 KB Output is correct
26 Correct 6664 ms 119752 KB Output is correct
27 Correct 6249 ms 119752 KB Output is correct
28 Correct 2255 ms 95592 KB Output is correct
29 Correct 5200 ms 118104 KB Output is correct
30 Correct 4444 ms 117504 KB Output is correct
31 Correct 4605 ms 114968 KB Output is correct
32 Correct 5964 ms 113604 KB Output is correct
33 Execution timed out 10056 ms 145512 KB Time limit exceeded
34 Halted 0 ms 0 KB -