oj.uz

Submission #865814

# Submission time Handle Problem Language Result Execution time Memory
865814 2023-10-24T18:23:45 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 382 ms 44996 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);
}


void solve(){
  cin >> n >> m >> D;
  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;
    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);
  ll ans = 0;
  for(int i = 1; i <= m; ++i){
    ll cur = v[pos[i] - 1][0];
    int P = pos[i];
    auto it = active.lower_bound(P);
    int l, r;
   
    if(it == active.begin()) l = -1;
    else l = *prev(it);

    if(it == active.end()) r = -1;
    else r = *it;

    ll val = sum(1, m, 1, P, 1) * D - cur;
    if(l != -1){
      ll L = get(1, m, 1, l, 1).second;
      ans = max(ans, val - L);
    }
    if(r != -1){
      ll R = get(1, m, r, m, 1).first;
      ans = max(ans, R - val);
    }
    sett(1, m, P, 1, val);
    active.insert(P);
    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 'int main()':
Main.cpp:137:15: warning: unused variable 'aa' [-Wunused-variable]
  137 |   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 189 ms 42688 KB Output is correct
2 Correct 195 ms 44996 KB Output is correct
3 Correct 199 ms 44496 KB Output is correct
4 Correct 188 ms 42492 KB Output is correct
5 Correct 200 ms 43968 KB Output is correct
6 Correct 190 ms 42980 KB Output is correct
7 Correct 198 ms 43708 KB Output is correct
8 Correct 190 ms 42428 KB Output is correct
9 Correct 190 ms 42464 KB Output is correct
10 Correct 195 ms 44928 KB Output is correct
11 Correct 192 ms 43288 KB Output is correct
12 Correct 194 ms 44228 KB Output is correct
13 Correct 197 ms 43288 KB Output is correct
14 Correct 202 ms 44480 KB Output is correct
15 Correct 193 ms 44220 KB Output is correct
16 Correct 188 ms 42968 KB Output is correct
17 Correct 193 ms 43716 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 42688 KB Output is correct
2 Correct 195 ms 44996 KB Output is correct
3 Correct 199 ms 44496 KB Output is correct
4 Correct 188 ms 42492 KB Output is correct
5 Correct 200 ms 43968 KB Output is correct
6 Correct 190 ms 42980 KB Output is correct
7 Correct 198 ms 43708 KB Output is correct
8 Correct 190 ms 42428 KB Output is correct
9 Correct 190 ms 42464 KB Output is correct
10 Correct 195 ms 44928 KB Output is correct
11 Correct 192 ms 43288 KB Output is correct
12 Correct 194 ms 44228 KB Output is correct
13 Correct 197 ms 43288 KB Output is correct
14 Correct 202 ms 44480 KB Output is correct
15 Correct 193 ms 44220 KB Output is correct
16 Correct 188 ms 42968 KB Output is correct
17 Correct 193 ms 43716 KB Output is correct
18 Incorrect 382 ms 43644 KB Output isn't correct
19 Halted 0 ms 0 KB -