oj.uz

Submission #864596

# Submission time Handle Problem Language Result Execution time Memory
864596 2023-10-23T09:55:52 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 353 ms 43204 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, 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

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 40748 KB Output is correct
2 Correct 184 ms 42432 KB Output is correct
3 Correct 174 ms 42436 KB Output is correct
4 Correct 164 ms 40488 KB Output is correct
5 Correct 183 ms 42220 KB Output is correct
6 Correct 165 ms 40712 KB Output is correct
7 Correct 176 ms 41656 KB Output is correct
8 Correct 170 ms 41188 KB Output is correct
9 Correct 168 ms 40652 KB Output is correct
10 Correct 183 ms 42796 KB Output is correct
11 Correct 170 ms 41188 KB Output is correct
12 Correct 186 ms 42180 KB Output is correct
13 Correct 170 ms 40488 KB Output is correct
14 Correct 181 ms 43204 KB Output is correct
15 Correct 181 ms 43204 KB Output is correct
16 Correct 173 ms 40744 KB Output is correct
17 Correct 183 ms 41660 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 40748 KB Output is correct
2 Correct 184 ms 42432 KB Output is correct
3 Correct 174 ms 42436 KB Output is correct
4 Correct 164 ms 40488 KB Output is correct
5 Correct 183 ms 42220 KB Output is correct
6 Correct 165 ms 40712 KB Output is correct
7 Correct 176 ms 41656 KB Output is correct
8 Correct 170 ms 41188 KB Output is correct
9 Correct 168 ms 40652 KB Output is correct
10 Correct 183 ms 42796 KB Output is correct
11 Correct 170 ms 41188 KB Output is correct
12 Correct 186 ms 42180 KB Output is correct
13 Correct 170 ms 40488 KB Output is correct
14 Correct 181 ms 43204 KB Output is correct
15 Correct 181 ms 43204 KB Output is correct
16 Correct 173 ms 40744 KB Output is correct
17 Correct 183 ms 41660 KB Output is correct
18 Incorrect 353 ms 41660 KB Output isn't correct
19 Halted 0 ms 0 KB -