oj.uz

Submission #1025246

# Submission time Handle Problem Language Result Execution time Memory
1025246 2024-07-16T18:16:45 Z NintsiChkhaidze Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 242880 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")
#define int ll
using namespace std;
 
const int N = 3e5 + 5,inf = 1e18;
pii t[4][3*N];
int x[N],y[N],yy[N],n,k;
multiset <int> st[4][3*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++){
    if (tot > k) return tot;
    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];
    scanf("%lld%lld",&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)
    printf("%lld\n",x);
    // cout<<x<<endl;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:109: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]
  109 |   for (int i=0;i<vec.size();i++){
      |                ~^~~~~~~~~~~
road_construction.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%lld%lld",&x[i],&y[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2567 ms 174304 KB Output is correct
2 Correct 2408 ms 174744 KB Output is correct
3 Correct 2290 ms 174796 KB Output is correct
4 Correct 2404 ms 174748 KB Output is correct
5 Correct 2523 ms 173724 KB Output is correct
6 Correct 67 ms 170120 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9660 ms 226208 KB Output is correct
2 Correct 9560 ms 225636 KB Output is correct
3 Correct 2718 ms 174544 KB Output is correct
4 Correct 9992 ms 224632 KB Output is correct
5 Correct 9095 ms 226208 KB Output is correct
6 Correct 7735 ms 231688 KB Output is correct
7 Correct 8415 ms 230924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6482 ms 242796 KB Output is correct
2 Correct 6580 ms 242880 KB Output is correct
3 Correct 35 ms 178772 KB Output is correct
4 Correct 2485 ms 227124 KB Output is correct
5 Correct 4789 ms 226956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6482 ms 242796 KB Output is correct
2 Correct 6580 ms 242880 KB Output is correct
3 Correct 35 ms 178772 KB Output is correct
4 Correct 2485 ms 227124 KB Output is correct
5 Correct 4789 ms 226956 KB Output is correct
6 Correct 7084 ms 242792 KB Output is correct
7 Correct 6471 ms 242624 KB Output is correct
8 Correct 35 ms 178776 KB Output is correct
9 Correct 31 ms 178772 KB Output is correct
10 Correct 6237 ms 240832 KB Output is correct
11 Correct 2076 ms 227012 KB Output is correct
12 Correct 4090 ms 227172 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2567 ms 174304 KB Output is correct
2 Correct 2408 ms 174744 KB Output is correct
3 Correct 2290 ms 174796 KB Output is correct
4 Correct 2404 ms 174748 KB Output is correct
5 Correct 2523 ms 173724 KB Output is correct
6 Correct 67 ms 170120 KB Output is correct
7 Correct 7234 ms 212516 KB Output is correct
8 Correct 6809 ms 212488 KB Output is correct
9 Correct 2285 ms 183604 KB Output is correct
10 Correct 5460 ms 209984 KB Output is correct
11 Correct 5322 ms 209204 KB Output is correct
12 Correct 6259 ms 205504 KB Output is correct
13 Correct 8553 ms 204704 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2567 ms 174304 KB Output is correct
2 Correct 2408 ms 174744 KB Output is correct
3 Correct 2290 ms 174796 KB Output is correct
4 Correct 2404 ms 174748 KB Output is correct
5 Correct 2523 ms 173724 KB Output is correct
6 Correct 67 ms 170120 KB Output is correct
7 Correct 9660 ms 226208 KB Output is correct
8 Correct 9560 ms 225636 KB Output is correct
9 Correct 2718 ms 174544 KB Output is correct
10 Correct 9992 ms 224632 KB Output is correct
11 Correct 9095 ms 226208 KB Output is correct
12 Correct 7735 ms 231688 KB Output is correct
13 Correct 8415 ms 230924 KB Output is correct
14 Correct 6482 ms 242796 KB Output is correct
15 Correct 6580 ms 242880 KB Output is correct
16 Correct 35 ms 178772 KB Output is correct
17 Correct 2485 ms 227124 KB Output is correct
18 Correct 4789 ms 226956 KB Output is correct
19 Correct 7084 ms 242792 KB Output is correct
20 Correct 6471 ms 242624 KB Output is correct
21 Correct 35 ms 178776 KB Output is correct
22 Correct 31 ms 178772 KB Output is correct
23 Correct 6237 ms 240832 KB Output is correct
24 Correct 2076 ms 227012 KB Output is correct
25 Correct 4090 ms 227172 KB Output is correct
26 Correct 7234 ms 212516 KB Output is correct
27 Correct 6809 ms 212488 KB Output is correct
28 Correct 2285 ms 183604 KB Output is correct
29 Correct 5460 ms 209984 KB Output is correct
30 Correct 5322 ms 209204 KB Output is correct
31 Correct 6259 ms 205504 KB Output is correct
32 Correct 8553 ms 204704 KB Output is correct
33 Execution timed out 10099 ms 242620 KB Time limit exceeded
34 Halted 0 ms 0 KB -