oj.uz

Submission #864598

# Submission time Handle Problem Language Result Execution time Memory
864598 2023-10-23T10:01:52 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 356 ms 41408 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, 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 8536 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 8536 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 166 ms 39056 KB Output is correct
2 Correct 180 ms 41148 KB Output is correct
3 Correct 169 ms 41408 KB Output is correct
4 Correct 160 ms 38724 KB Output is correct
5 Correct 178 ms 40128 KB Output is correct
6 Correct 164 ms 39524 KB Output is correct
7 Correct 170 ms 40140 KB Output is correct
8 Correct 168 ms 38552 KB Output is correct
9 Correct 168 ms 38380 KB Output is correct
10 Correct 182 ms 40808 KB Output is correct
11 Correct 170 ms 39204 KB Output is correct
12 Correct 180 ms 40316 KB Output is correct
13 Correct 164 ms 38328 KB Output is correct
14 Correct 179 ms 40636 KB Output is correct
15 Correct 179 ms 40488 KB Output is correct
16 Correct 163 ms 38440 KB Output is correct
17 Correct 177 ms 40380 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 39056 KB Output is correct
2 Correct 180 ms 41148 KB Output is correct
3 Correct 169 ms 41408 KB Output is correct
4 Correct 160 ms 38724 KB Output is correct
5 Correct 178 ms 40128 KB Output is correct
6 Correct 164 ms 39524 KB Output is correct
7 Correct 170 ms 40140 KB Output is correct
8 Correct 168 ms 38552 KB Output is correct
9 Correct 168 ms 38380 KB Output is correct
10 Correct 182 ms 40808 KB Output is correct
11 Correct 170 ms 39204 KB Output is correct
12 Correct 180 ms 40316 KB Output is correct
13 Correct 164 ms 38328 KB Output is correct
14 Correct 179 ms 40636 KB Output is correct
15 Correct 179 ms 40488 KB Output is correct
16 Correct 163 ms 38440 KB Output is correct
17 Correct 177 ms 40380 KB Output is correct
18 Incorrect 356 ms 39148 KB Output isn't correct
19 Halted 0 ms 0 KB -