oj.uz

Submission #1025218

# Submission time Handle Problem Language Result Execution time Memory
1025218 2024-07-16T17:58:26 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 298700 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
#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);
  for (int i = 1; i<= n; i++){
    arr[i] = {x[i],i};
  }
  sort(arr+1,arr+n+1);
  
  int tot = 0;
  for (int i = 1; i <= n; i++){
    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]];

  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:111: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]
  111 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2829 ms 231224 KB Output is correct
2 Correct 2578 ms 231100 KB Output is correct
3 Correct 2505 ms 231116 KB Output is correct
4 Correct 2583 ms 231344 KB Output is correct
5 Correct 2494 ms 230076 KB Output is correct
6 Correct 95 ms 226400 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10054 ms 280968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10018 ms 298700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10018 ms 298700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2829 ms 231224 KB Output is correct
2 Correct 2578 ms 231100 KB Output is correct
3 Correct 2505 ms 231116 KB Output is correct
4 Correct 2583 ms 231344 KB Output is correct
5 Correct 2494 ms 230076 KB Output is correct
6 Correct 95 ms 226400 KB Output is correct
7 Correct 8392 ms 261576 KB Output is correct
8 Correct 8503 ms 261556 KB Output is correct
9 Correct 2625 ms 231096 KB Output is correct
10 Correct 7661 ms 258976 KB Output is correct
11 Correct 8037 ms 258292 KB Output is correct
12 Correct 7141 ms 254660 KB Output is correct
13 Correct 9042 ms 253896 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2829 ms 231224 KB Output is correct
2 Correct 2578 ms 231100 KB Output is correct
3 Correct 2505 ms 231116 KB Output is correct
4 Correct 2583 ms 231344 KB Output is correct
5 Correct 2494 ms 230076 KB Output is correct
6 Correct 95 ms 226400 KB Output is correct
7 Execution timed out 10054 ms 280968 KB Time limit exceeded
8 Halted 0 ms 0 KB -