oj.uz

Submission #864597

# Submission time Handle Problem Language Result Execution time Memory
864597 2023-10-23T10:01:11 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 365 ms 41268 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int n, m, pos[N];
ll D, L[N], R[N], lazyl[N], lazyr[N];
void build(int l, int r, int k){
  // cout << l << ' ' << r << endl;
  if(l == r){
    L[k] = R[k] = lazyl[k] = lazyr[k] = 0;
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
  L[k] = R[k] = lazyl[k] = lazyr[k] = 0;
}
void pushL(int k){
  lazyl[k<<1] += lazyl[k];
  lazyl[k<<1|1] += lazyl[k];
  L[k<<1] += lazyl[k];
  L[k<<1|1] += lazyl[k];
  lazyl[k] = 0;
}
void pushR(int k){
  lazyr[k<<1] += lazyr[k];
  lazyr[k<<1|1] += lazyr[k];
  R[k<<1] += lazyr[k];
  R[k<<1|1] += lazyr[k];
  lazyr[k] = 0;
}
void updateL(int l, int r, int ql, int qr, int k, ll val){
  if(ql > r || r > ql) return;
  if(ql <= l && r <= qr){
    L[k] += val;
    lazyl[k] += val;
    return;
  }
  pushL(k);
  int mid = l+r>>1;
  updateL(l, mid, ql, qr, k<<1, val);
  updateL(mid+1, r, ql, qr, k<<1|1, val);
}
void updateR(int l, int r, int ql, int qr, int k, ll val){
  if(ql > r || r > ql) return;
  if(ql <= l && r <= qr){
    R[k] += val;
    lazyr[k] += val;
    return;
  }
  pushR(k);
  int mid = l+r>>1;
  updateR(l, mid, ql, qr, k<<1, val);
  updateR(mid+1, r, ql, qr, k<<1|1, val);
}
void sett(int l, int r, int p, int k, ll x, ll y){
  if(l == r){
    L[k] = x;
    R[k] = y;
    return;
  }
  pushL(k);
  pushR(k);
  int mid = l+r>>1;
  if(p <= mid)
    sett(l, mid, p, k<<1, x, y);
  else
    sett(mid+1, r, p, k<<1|1, x, y);
}
pair<ll, ll> get(int l, int r, int p, int k){
  if(l == r){
    return {L[k], R[k]};
  }
  pushL(k);
  pushR(k);
  int mid = l+r>>1;
  if(p <= mid)
    return get(l, mid, p, k<<1);
  return get(mid+1, r, p, k<<1|1);
}

void solve(){
  cin >> n >> m >> D;
  D *= 2;
  ll ans = 0;
  for(int i = 0; i < n; ++i){
    int x; cin >> x;
  }
  vector<array<ll, 2>> v;
  for(int i = 1; i <= m; ++i){
    ll x; cin >> x;
    x *= 2;
    v.pb({x, i});
  }
  sort(all(v));
  for(int i = 0; i < m; ++i) pos[v[i][1]] = i + 1;
  set<int> active;
  build(1, m, 1);

  for(int i = 0; i < m; ++i){
    ll cur = v[pos[i]][0];
    int P = pos[i];
    auto it = active.lower_bound(P);
    int l, r;
    ll left_left, left_right, right_right, right_left;
    if(it == active.begin()){
      l = -1;
      left_left = -1e18;
      left_right = -1e18;
    }else{
      l = *prev(it);
      auto x = get(1, m, l, 1);
      left_left = x.first;
      left_right = x.second;
    }
    if(it == active.end()){
      r = -1;
      right_left = 1e18;
      right_right = 1e18;
    }else{
      r = *it;
      auto x = get(1, m, r, 1);
      right_left = x.first;
      right_right = x.second;
    }
    // cout << l << ' ' << r << '\n';
    ll addL = 0, addR = 1e17, add = 1e17;
    // cout << left_left << ' ' << left_right << '\n';
    while(addL <= addR){
      ll addM = addL+addR>>1;
      bool ok = 1;
      pair<ll, ll> range = {left_left - addM + D, right_right + addM - D};
      
      if(range.first > range.second){
        ok = 0;
      }else if(range.second < cur - addM - ans || range.first > cur + addM + ans){
        ok = 0;
      }
      if(ok){
        add = addM;
        addR = addM - 1;
      }else{
        addL = addM + 1;
      }
    }
    pair<ll, ll> range = {left_left - add + D, right_right + add - D};
    ans += add;
    pair<ll, ll> val = {max(cur - ans, range.first), min(cur + ans, range.second)};
    // cout << "val:" << cur << ' ' << val.first << ' ' << val.second << '\n';
    sett(1, m, P, 1, val.first, val.second);
    if(l != -1){
      updateL(1, m, 1, l, 1, -add);
      ll A = val.second - D - get(1, m, l, 1).second;
      if(A < 0){
        updateR(1, m, 1, l, 1, A);
      }
    }
    if(r != -1){
      updateR(1, m, r, m, 1, add);
      ll A = get(1, m, l, 1).first - (val.first + D);
      if(A < 0){
        updateL(1, m, r, m, 1, -A);
      }

    }

    active.insert(P);
    if(ans % 2 == 0) cout << ans / 2 << ' ';
    else cout << ans/2 << ".5" << ' ';
    // for(auto k: active) cout << k << ' ';
      // en;
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateL(int, int, int, int, int, long long int)':
Main.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateR(int, int, int, int, int, long long int)':
Main.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void sett(int, int, int, int, long long int, long long int)':
Main.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, int)':
Main.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void solve()':
Main.cpp:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |       ll addM = addL+addR>>1;
      |                 ~~~~^~~~~
Main.cpp:112:19: warning: variable 'left_right' set but not used [-Wunused-but-set-variable]
  112 |     ll left_left, left_right, right_right, right_left;
      |                   ^~~~~~~~~~
Main.cpp:112:44: warning: variable 'right_left' set but not used [-Wunused-but-set-variable]
  112 |     ll left_left, left_right, right_right, right_left;
      |                                            ^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:185:15: warning: unused variable 'aa' [-Wunused-variable]
  185 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 39912 KB Output is correct
2 Correct 182 ms 40644 KB Output is correct
3 Correct 171 ms 41124 KB Output is correct
4 Correct 165 ms 38408 KB Output is correct
5 Correct 177 ms 40128 KB Output is correct
6 Correct 163 ms 39040 KB Output is correct
7 Correct 176 ms 39872 KB Output is correct
8 Correct 162 ms 38764 KB Output is correct
9 Correct 164 ms 38336 KB Output is correct
10 Correct 186 ms 41032 KB Output is correct
11 Correct 171 ms 40132 KB Output is correct
12 Correct 182 ms 40128 KB Output is correct
13 Correct 171 ms 38696 KB Output is correct
14 Correct 181 ms 41268 KB Output is correct
15 Correct 181 ms 40148 KB Output is correct
16 Correct 164 ms 39360 KB Output is correct
17 Correct 185 ms 40432 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 39912 KB Output is correct
2 Correct 182 ms 40644 KB Output is correct
3 Correct 171 ms 41124 KB Output is correct
4 Correct 165 ms 38408 KB Output is correct
5 Correct 177 ms 40128 KB Output is correct
6 Correct 163 ms 39040 KB Output is correct
7 Correct 176 ms 39872 KB Output is correct
8 Correct 162 ms 38764 KB Output is correct
9 Correct 164 ms 38336 KB Output is correct
10 Correct 186 ms 41032 KB Output is correct
11 Correct 171 ms 40132 KB Output is correct
12 Correct 182 ms 40128 KB Output is correct
13 Correct 171 ms 38696 KB Output is correct
14 Correct 181 ms 41268 KB Output is correct
15 Correct 181 ms 40148 KB Output is correct
16 Correct 164 ms 39360 KB Output is correct
17 Correct 185 ms 40432 KB Output is correct
18 Incorrect 365 ms 39288 KB Output isn't correct
19 Halted 0 ms 0 KB -