oj.uz

Submission #865815

# Submission time Handle Problem Language Result Execution time Memory
865815 2023-10-24T18:25:48 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 396 ms 43456 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) + 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);
    if(P < m)
      update(1, m, P + 1, m, 1, D);
    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:139:15: warning: unused variable 'aa' [-Wunused-variable]
  139 |   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 233 ms 40640 KB Output is correct
2 Correct 231 ms 42688 KB Output is correct
3 Correct 236 ms 42684 KB Output is correct
4 Correct 224 ms 41292 KB Output is correct
5 Correct 236 ms 41876 KB Output is correct
6 Correct 228 ms 40896 KB Output is correct
7 Correct 234 ms 41920 KB Output is correct
8 Correct 227 ms 40668 KB Output is correct
9 Correct 228 ms 40380 KB Output is correct
10 Correct 241 ms 43456 KB Output is correct
11 Correct 232 ms 41920 KB Output is correct
12 Correct 232 ms 42168 KB Output is correct
13 Correct 231 ms 40380 KB Output is correct
14 Correct 231 ms 42432 KB Output is correct
15 Correct 231 ms 42396 KB Output is correct
16 Correct 227 ms 40724 KB Output is correct
17 Correct 236 ms 42044 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 40640 KB Output is correct
2 Correct 231 ms 42688 KB Output is correct
3 Correct 236 ms 42684 KB Output is correct
4 Correct 224 ms 41292 KB Output is correct
5 Correct 236 ms 41876 KB Output is correct
6 Correct 228 ms 40896 KB Output is correct
7 Correct 234 ms 41920 KB Output is correct
8 Correct 227 ms 40668 KB Output is correct
9 Correct 228 ms 40380 KB Output is correct
10 Correct 241 ms 43456 KB Output is correct
11 Correct 232 ms 41920 KB Output is correct
12 Correct 232 ms 42168 KB Output is correct
13 Correct 231 ms 40380 KB Output is correct
14 Correct 231 ms 42432 KB Output is correct
15 Correct 231 ms 42396 KB Output is correct
16 Correct 227 ms 40724 KB Output is correct
17 Correct 236 ms 42044 KB Output is correct
18 Incorrect 396 ms 40848 KB Output isn't correct
19 Halted 0 ms 0 KB -