oj.uz

답안 #1025271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025271 2024-07-16T18:57:58 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 145712 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;
int idx;
bool z;
 
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;
 
    int id = arr[i].s,v1 = x[id] + y[id];
    while (tot <= k){
      L = 1; R = yy[id];
      pli res = get(0,1,1,n);
      ll 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);
    }
 
    int v2 = x[id] - y[id];
    while (tot <= k){
      L = yy[id] + 1; R = n;
      pli res = get(1,1,1,n);
      ll 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);
    }
 
    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:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2470 ms 95400 KB Output is correct
2 Correct 2406 ms 95444 KB Output is correct
3 Correct 2475 ms 95444 KB Output is correct
4 Correct 2488 ms 95444 KB Output is correct
5 Correct 2469 ms 94376 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6978 ms 137424 KB Output is correct
2 Correct 7687 ms 136904 KB Output is correct
3 Correct 2449 ms 95384 KB Output is correct
4 Correct 7029 ms 136772 KB Output is correct
5 Correct 6983 ms 137000 KB Output is correct
6 Correct 6365 ms 136908 KB Output is correct
7 Correct 5900 ms 136564 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5051 ms 145712 KB Output is correct
2 Correct 5034 ms 145580 KB Output is correct
3 Correct 14 ms 90716 KB Output is correct
4 Correct 1791 ms 133848 KB Output is correct
5 Correct 3633 ms 133864 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5051 ms 145712 KB Output is correct
2 Correct 5034 ms 145580 KB Output is correct
3 Correct 14 ms 90716 KB Output is correct
4 Correct 1791 ms 133848 KB Output is correct
5 Correct 3633 ms 133864 KB Output is correct
6 Correct 5636 ms 145584 KB Output is correct
7 Correct 5429 ms 145576 KB Output is correct
8 Correct 14 ms 90716 KB Output is correct
9 Correct 14 ms 90716 KB Output is correct
10 Correct 5423 ms 144216 KB Output is correct
11 Correct 1605 ms 133832 KB Output is correct
12 Correct 3543 ms 133864 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2470 ms 95400 KB Output is correct
2 Correct 2406 ms 95444 KB Output is correct
3 Correct 2475 ms 95444 KB Output is correct
4 Correct 2488 ms 95444 KB Output is correct
5 Correct 2469 ms 94376 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct
7 Correct 6683 ms 119748 KB Output is correct
8 Correct 7431 ms 119740 KB Output is correct
9 Correct 2376 ms 95520 KB Output is correct
10 Correct 5207 ms 117916 KB Output is correct
11 Correct 4441 ms 117372 KB Output is correct
12 Correct 5009 ms 114968 KB Output is correct
13 Correct 6735 ms 113536 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2470 ms 95400 KB Output is correct
2 Correct 2406 ms 95444 KB Output is correct
3 Correct 2475 ms 95444 KB Output is correct
4 Correct 2488 ms 95444 KB Output is correct
5 Correct 2469 ms 94376 KB Output is correct
6 Correct 34 ms 90716 KB Output is correct
7 Correct 6978 ms 137424 KB Output is correct
8 Correct 7687 ms 136904 KB Output is correct
9 Correct 2449 ms 95384 KB Output is correct
10 Correct 7029 ms 136772 KB Output is correct
11 Correct 6983 ms 137000 KB Output is correct
12 Correct 6365 ms 136908 KB Output is correct
13 Correct 5900 ms 136564 KB Output is correct
14 Correct 5051 ms 145712 KB Output is correct
15 Correct 5034 ms 145580 KB Output is correct
16 Correct 14 ms 90716 KB Output is correct
17 Correct 1791 ms 133848 KB Output is correct
18 Correct 3633 ms 133864 KB Output is correct
19 Correct 5636 ms 145584 KB Output is correct
20 Correct 5429 ms 145576 KB Output is correct
21 Correct 14 ms 90716 KB Output is correct
22 Correct 14 ms 90716 KB Output is correct
23 Correct 5423 ms 144216 KB Output is correct
24 Correct 1605 ms 133832 KB Output is correct
25 Correct 3543 ms 133864 KB Output is correct
26 Correct 6683 ms 119748 KB Output is correct
27 Correct 7431 ms 119740 KB Output is correct
28 Correct 2376 ms 95520 KB Output is correct
29 Correct 5207 ms 117916 KB Output is correct
30 Correct 4441 ms 117372 KB Output is correct
31 Correct 5009 ms 114968 KB Output is correct
32 Correct 6735 ms 113536 KB Output is correct
33 Execution timed out 10071 ms 145592 KB Time limit exceeded
34 Halted 0 ms 0 KB -