oj.uz

Submission #865823

# Submission time Handle Problem Language Result Execution time Memory
865823 2023-10-24T18:56:37 Z mychecksedad Measures (CEOI22_measures) C++17
100 / 100
 312 ms 34500 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], co[N];
ll D, T[N][2], lazy[N][2];
void build(int l, int r, int k){
  lazy[k][0] = lazy[k][1] = 0;
  co[k] = 0;
  if(l == r){
    T[k][0] = -1e18;
    T[k][1] = 1e18;
    co[k] = 0;
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
  T[k][0] = -1e18;
  T[k][1] = 1e18;
}
void push(int k){
  for(int r = 0; r < 2; ++r){
    lazy[k<<1][r] += lazy[k][r];
    lazy[k<<1|1][r] += lazy[k][r];
    T[k<<1][r] += lazy[k][r];
    T[k<<1|1][r] += lazy[k][r];
    lazy[k][r] = 0;
  }
}
void sett(int l, int r, int p, int k, ll val){
  if(l == r){
    T[k][0] = val;
    T[k][1] = val;
    co[k] = 1;
    return;
  }
  push(k);
  int mid = l+r>>1;
  if(p <= mid)
    sett(l, mid, p, k<<1, val);
  else
    sett(mid+1, r, p, k<<1|1, val);
  T[k][0] = max(T[k<<1][0], T[k<<1|1][0]);
  T[k][1] = min(T[k<<1][1], T[k<<1|1][1]);
  co[k] = co[k<<1] + co[k<<1|1];
}
void update(int l, int r, int ql, int qr, int k, ll add){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T[k][0] += add;
    T[k][1] += add;
    lazy[k][0] += add;
    lazy[k][1] += add;
    return;
  }
  push(k);
  int mid = l+r>>1;
  update(l, mid, ql, qr, k<<1, add);
  update(mid+1, r, ql, qr, k<<1|1, add);
  T[k][0] = max(T[k<<1][0], T[k<<1|1][0]);
  T[k][1] = min(T[k<<1][1], T[k<<1|1][1]);
  co[k] = co[k<<1] + co[k<<1|1];
}
pair<ll, ll> get(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return {(ll)-1e18, (ll)1e18};
  if(ql <= l && r <= qr) return {T[k][0], T[k][1]};
  push(k);
  int mid = l+r>>1;
  auto v1 = get(l, mid, ql, qr, k<<1); 
  auto v2 = get(mid+1, r, ql, qr, k<<1|1); 
  return {max(v1.first, v2.first), min(v1.second, v2.second)};
}
int sum(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return co[k];
  push(k);
  int mid = l+r>>1;
  return sum(l, mid, ql, qr, k<<1) + sum(mid+1, r, ql, qr, k<<1|1);
}

bool check(ll m, vector<ll> &v){
  ll last = 1e18;
  for(int i = v.size() - 1; i >= 0; --i){
    if(last < v[i] - m){
      return 0;
    }
    last = min(last - D, v[i] + m - D);
  }
  return 1;
}
ll solv(vector<ll> &v){
  sort(all(v));
  ll l = 0, r = 1e18, ans = 1e18;
  while(l <= r){
    ll m = l+r>>1;
    if(check(m, v)){
      ans = m;
      r = m - 1;
    }else l = m + 1;
  }
  return ans;
}

void solve(){
  cin >> n >> m >> D;
  if(n > 0){
    D *= 2;
    vector<ll> POS(n);
    for(int i = 0; i < n; ++i){
      cin >> POS[i];
      POS[i] *= 2;
    }
    for(int i = 1; i <= m; ++i){
      ll x; cin >> x;
      POS.pb(2*x);
      ll ans = solv(POS);
      if(ans % 2 == 0) cout << ans / 2 << ' ';
      else cout << ans/2 << ".5" << ' ';
    }
    return;
  }
  vector<array<ll, 2>> v;
  for(int i = 0; i < m; ++i){
    ll x; cin >> x;
    v.pb({x, i});
  }
  sort(all(v));
  for(int i = 0; i < m; ++i) pos[v[i][1]] = i;
  build(1, m, 1);
  ll ans = 0;
  for(int i = 0; i < m; ++i){
    ll cur = v[pos[i]][0];
    int P = pos[i] + 1;
   
    update(1, m, P + 1, m, 1, D);

    ll val = (sum(1, m, 1, P, 1) + 1) * D - cur;

    ll L = get(1, m, 1, P - 1, 1).second;
    ans = max(ans, val - L);

    ll R = get(1, m, P + 1, m, 1).first;
    ans = max(ans, R - val);

    ans = max(ans, R - L);

    sett(1, m, P, 1, val);
    if(ans % 2 == 0) cout << ans / 2 << ' ';
    else cout << ans/2 << ".5" << ' ';
    // for(auto k: active) cout << k << ' ';
  }
}


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:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void sett(int, int, int, int, long long int)':
Main.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void update(int, int, int, int, int, long long int)':
Main.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, int, int)':
Main.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'int sum(int, int, int, int, int)':
Main.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int solv(std::vector<long long int>&)':
Main.cpp:103:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |     ll m = l+r>>1;
      |            ~^~
Main.cpp: In function 'int main()':
Main.cpp:165:15: warning: unused variable 'aa' [-Wunused-variable]
  165 |   int tt = 1, aa;
      |               ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 221 ms 9560 KB Output is correct
10 Correct 266 ms 10580 KB Output is correct
11 Correct 168 ms 9564 KB Output is correct
12 Correct 281 ms 10832 KB Output is correct
13 Correct 164 ms 9052 KB Output is correct
14 Correct 209 ms 9548 KB Output is correct
15 Correct 215 ms 9560 KB Output is correct
16 Correct 167 ms 9564 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 31756 KB Output is correct
2 Correct 214 ms 33724 KB Output is correct
3 Correct 216 ms 33772 KB Output is correct
4 Correct 210 ms 31680 KB Output is correct
5 Correct 210 ms 33056 KB Output is correct
6 Correct 209 ms 32448 KB Output is correct
7 Correct 212 ms 32636 KB Output is correct
8 Correct 208 ms 31936 KB Output is correct
9 Correct 216 ms 31420 KB Output is correct
10 Correct 217 ms 34500 KB Output is correct
11 Correct 210 ms 32688 KB Output is correct
12 Correct 217 ms 33700 KB Output is correct
13 Correct 213 ms 31184 KB Output is correct
14 Correct 212 ms 34008 KB Output is correct
15 Correct 212 ms 32956 KB Output is correct
16 Correct 208 ms 31340 KB Output is correct
17 Correct 215 ms 32684 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 31756 KB Output is correct
2 Correct 214 ms 33724 KB Output is correct
3 Correct 216 ms 33772 KB Output is correct
4 Correct 210 ms 31680 KB Output is correct
5 Correct 210 ms 33056 KB Output is correct
6 Correct 209 ms 32448 KB Output is correct
7 Correct 212 ms 32636 KB Output is correct
8 Correct 208 ms 31936 KB Output is correct
9 Correct 216 ms 31420 KB Output is correct
10 Correct 217 ms 34500 KB Output is correct
11 Correct 210 ms 32688 KB Output is correct
12 Correct 217 ms 33700 KB Output is correct
13 Correct 213 ms 31184 KB Output is correct
14 Correct 212 ms 34008 KB Output is correct
15 Correct 212 ms 32956 KB Output is correct
16 Correct 208 ms 31340 KB Output is correct
17 Correct 215 ms 32684 KB Output is correct
18 Correct 294 ms 31680 KB Output is correct
19 Correct 305 ms 33844 KB Output is correct
20 Correct 215 ms 33472 KB Output is correct
21 Correct 250 ms 31932 KB Output is correct
22 Correct 256 ms 31628 KB Output is correct
23 Correct 216 ms 32192 KB Output is correct
24 Correct 312 ms 32196 KB Output is correct
25 Correct 210 ms 31188 KB Output is correct
26 Correct 305 ms 31680 KB Output is correct
27 Correct 305 ms 33628 KB Output is correct
28 Correct 261 ms 31752 KB Output is correct
29 Correct 280 ms 33220 KB Output is correct
30 Correct 250 ms 31164 KB Output is correct
31 Correct 261 ms 33140 KB Output is correct
32 Correct 220 ms 32888 KB Output is correct
33 Correct 299 ms 32176 KB Output is correct
34 Correct 256 ms 32444 KB Output is correct