Submission #864596

#	Time	Username	Problem	Language	Result	Execution time	Memory
864596		mychecksedad	Measures (CEOI22_measures)	C++17	35 / 100	353 ms	43204 KiB

Main

/* 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, 1, l, 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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41