oj.uz

Submission #864599

# Submission time Handle Problem Language Result Execution time Memory
864599 2023-10-23T10:04:59 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 372 ms 41416 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';
    updateL(1, m, 1, m, 1, -add);
    updateR(1, m, 1, m, 1, add);
    sett(1, m, P, 1, val.first, val.second);
    if(l != -1){
      ll A = val.second - D - get(1, m, l, 1).second;
      if(A < 0){
        updateR(1, m, 1, l, 1, A);
      }
    }
    if(r != -1){
      ll A = get(1, m, r, 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 164 ms 38592 KB Output is correct
2 Correct 180 ms 41416 KB Output is correct
3 Correct 170 ms 40892 KB Output is correct
4 Correct 161 ms 38316 KB Output is correct
5 Correct 180 ms 40208 KB Output is correct
6 Correct 164 ms 38816 KB Output is correct
7 Correct 169 ms 39744 KB Output is correct
8 Correct 168 ms 39188 KB Output is correct
9 Correct 163 ms 38452 KB Output is correct
10 Correct 180 ms 40884 KB Output is correct
11 Correct 172 ms 40180 KB Output is correct
12 Correct 178 ms 40268 KB Output is correct
13 Correct 163 ms 39616 KB Output is correct
14 Correct 206 ms 40760 KB Output is correct
15 Correct 183 ms 40172 KB Output is correct
16 Correct 162 ms 38336 KB Output is correct
17 Correct 183 ms 40336 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 38592 KB Output is correct
2 Correct 180 ms 41416 KB Output is correct
3 Correct 170 ms 40892 KB Output is correct
4 Correct 161 ms 38316 KB Output is correct
5 Correct 180 ms 40208 KB Output is correct
6 Correct 164 ms 38816 KB Output is correct
7 Correct 169 ms 39744 KB Output is correct
8 Correct 168 ms 39188 KB Output is correct
9 Correct 163 ms 38452 KB Output is correct
10 Correct 180 ms 40884 KB Output is correct
11 Correct 172 ms 40180 KB Output is correct
12 Correct 178 ms 40268 KB Output is correct
13 Correct 163 ms 39616 KB Output is correct
14 Correct 206 ms 40760 KB Output is correct
15 Correct 183 ms 40172 KB Output is correct
16 Correct 162 ms 38336 KB Output is correct
17 Correct 183 ms 40336 KB Output is correct
18 Incorrect 372 ms 39244 KB Output isn't correct
19 Halted 0 ms 0 KB -