oj.uz

답안 #1025275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025275 2024-07-16T19:01:04 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145608 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 + 5;
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;
 
  for (int 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;
      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;
      roll.pb({{1,res.s},{res.f,-inf}});
      oldval = res.f;
      newval = -inf;
      idx = res.s;
      z = 0;
      upd(1,1,1,n);
    }
    if (tot > k) return tot;
 
    for (int 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:134:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2944 ms 95392 KB Output is correct
2 Correct 2954 ms 95400 KB Output is correct
3 Correct 2909 ms 95372 KB Output is correct
4 Correct 2989 ms 95612 KB Output is correct
5 Correct 2986 ms 94372 KB Output is correct
6 Correct 35 ms 90860 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8368 ms 137092 KB Output is correct
2 Correct 8944 ms 136580 KB Output is correct
3 Correct 3022 ms 95388 KB Output is correct
4 Correct 8016 ms 136840 KB Output is correct
5 Correct 8391 ms 136928 KB Output is correct
6 Correct 7731 ms 136564 KB Output is correct
7 Correct 7462 ms 136300 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5962 ms 145272 KB Output is correct
2 Correct 5852 ms 145608 KB Output is correct
3 Correct 14 ms 90712 KB Output is correct
4 Correct 2302 ms 133604 KB Output is correct
5 Correct 3900 ms 133872 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5962 ms 145272 KB Output is correct
2 Correct 5852 ms 145608 KB Output is correct
3 Correct 14 ms 90712 KB Output is correct
4 Correct 2302 ms 133604 KB Output is correct
5 Correct 3900 ms 133872 KB Output is correct
6 Correct 6039 ms 145580 KB Output is correct
7 Correct 5864 ms 145580 KB Output is correct
8 Correct 14 ms 90716 KB Output is correct
9 Correct 13 ms 90716 KB Output is correct
10 Correct 6249 ms 144216 KB Output is correct
11 Correct 1795 ms 133840 KB Output is correct
12 Correct 4247 ms 133872 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2944 ms 95392 KB Output is correct
2 Correct 2954 ms 95400 KB Output is correct
3 Correct 2909 ms 95372 KB Output is correct
4 Correct 2989 ms 95612 KB Output is correct
5 Correct 2986 ms 94372 KB Output is correct
6 Correct 35 ms 90860 KB Output is correct
7 Correct 7620 ms 119744 KB Output is correct
8 Correct 7377 ms 119732 KB Output is correct
9 Correct 2481 ms 95444 KB Output is correct
10 Correct 5951 ms 117984 KB Output is correct
11 Correct 5463 ms 117496 KB Output is correct
12 Correct 5198 ms 114964 KB Output is correct
13 Correct 6787 ms 113536 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2944 ms 95392 KB Output is correct
2 Correct 2954 ms 95400 KB Output is correct
3 Correct 2909 ms 95372 KB Output is correct
4 Correct 2989 ms 95612 KB Output is correct
5 Correct 2986 ms 94372 KB Output is correct
6 Correct 35 ms 90860 KB Output is correct
7 Correct 8368 ms 137092 KB Output is correct
8 Correct 8944 ms 136580 KB Output is correct
9 Correct 3022 ms 95388 KB Output is correct
10 Correct 8016 ms 136840 KB Output is correct
11 Correct 8391 ms 136928 KB Output is correct
12 Correct 7731 ms 136564 KB Output is correct
13 Correct 7462 ms 136300 KB Output is correct
14 Correct 5962 ms 145272 KB Output is correct
15 Correct 5852 ms 145608 KB Output is correct
16 Correct 14 ms 90712 KB Output is correct
17 Correct 2302 ms 133604 KB Output is correct
18 Correct 3900 ms 133872 KB Output is correct
19 Correct 6039 ms 145580 KB Output is correct
20 Correct 5864 ms 145580 KB Output is correct
21 Correct 14 ms 90716 KB Output is correct
22 Correct 13 ms 90716 KB Output is correct
23 Correct 6249 ms 144216 KB Output is correct
24 Correct 1795 ms 133840 KB Output is correct
25 Correct 4247 ms 133872 KB Output is correct
26 Correct 7620 ms 119744 KB Output is correct
27 Correct 7377 ms 119732 KB Output is correct
28 Correct 2481 ms 95444 KB Output is correct
29 Correct 5951 ms 117984 KB Output is correct
30 Correct 5463 ms 117496 KB Output is correct
31 Correct 5198 ms 114964 KB Output is correct
32 Correct 6787 ms 113536 KB Output is correct
33 Execution timed out 10020 ms 145512 KB Time limit exceeded
34 Halted 0 ms 0 KB -