oj.uz

Submission #1025223

# Submission time Handle Problem Language Result Execution time Memory
1025223 2024-07-16T18:01:35 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 293572 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
#pragma GCC optimize("Ofast")
#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);
  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]];

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2512 ms 231116 KB Output is correct
2 Correct 2455 ms 231272 KB Output is correct
3 Correct 2349 ms 231116 KB Output is correct
4 Correct 2419 ms 231332 KB Output is correct
5 Correct 2507 ms 230080 KB Output is correct
6 Correct 82 ms 226384 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10060 ms 277772 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 10022 ms 293572 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 10022 ms 293572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2512 ms 231116 KB Output is correct
2 Correct 2455 ms 231272 KB Output is correct
3 Correct 2349 ms 231116 KB Output is correct
4 Correct 2419 ms 231332 KB Output is correct
5 Correct 2507 ms 230080 KB Output is correct
6 Correct 82 ms 226384 KB Output is correct
7 Correct 7880 ms 259528 KB Output is correct
8 Correct 7886 ms 259584 KB Output is correct
9 Correct 2422 ms 231084 KB Output is correct
10 Correct 7765 ms 256944 KB Output is correct
11 Correct 6829 ms 256412 KB Output is correct
12 Correct 6797 ms 252732 KB Output is correct
13 Correct 8443 ms 251752 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2512 ms 231116 KB Output is correct
2 Correct 2455 ms 231272 KB Output is correct
3 Correct 2349 ms 231116 KB Output is correct
4 Correct 2419 ms 231332 KB Output is correct
5 Correct 2507 ms 230080 KB Output is correct
6 Correct 82 ms 226384 KB Output is correct
7 Execution timed out 10060 ms 277772 KB Time limit exceeded
8 Halted 0 ms 0 KB -