oj.uz

Submission #865816

# Submission time Handle Problem Language Result Execution time Memory
865816 2023-10-24T18:26:54 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 414 ms 43032 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;
    if(P < m)
      update(1, m, P + 1, m, 1, D);
    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);
    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:138:15: warning: unused variable 'aa' [-Wunused-variable]
  138 |   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 227 ms 41280 KB Output is correct
2 Correct 233 ms 43032 KB Output is correct
3 Correct 237 ms 42684 KB Output is correct
4 Correct 234 ms 40364 KB Output is correct
5 Correct 230 ms 42116 KB Output is correct
6 Correct 231 ms 41812 KB Output is correct
7 Correct 233 ms 42428 KB Output is correct
8 Correct 231 ms 40632 KB Output is correct
9 Correct 232 ms 40640 KB Output is correct
10 Correct 233 ms 42924 KB Output is correct
11 Correct 239 ms 42112 KB Output is correct
12 Correct 238 ms 42484 KB Output is correct
13 Correct 232 ms 40368 KB Output is correct
14 Correct 232 ms 42428 KB Output is correct
15 Correct 232 ms 42688 KB Output is correct
16 Correct 234 ms 40592 KB Output is correct
17 Correct 260 ms 41668 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 41280 KB Output is correct
2 Correct 233 ms 43032 KB Output is correct
3 Correct 237 ms 42684 KB Output is correct
4 Correct 234 ms 40364 KB Output is correct
5 Correct 230 ms 42116 KB Output is correct
6 Correct 231 ms 41812 KB Output is correct
7 Correct 233 ms 42428 KB Output is correct
8 Correct 231 ms 40632 KB Output is correct
9 Correct 232 ms 40640 KB Output is correct
10 Correct 233 ms 42924 KB Output is correct
11 Correct 239 ms 42112 KB Output is correct
12 Correct 238 ms 42484 KB Output is correct
13 Correct 232 ms 40368 KB Output is correct
14 Correct 232 ms 42428 KB Output is correct
15 Correct 232 ms 42688 KB Output is correct
16 Correct 234 ms 40592 KB Output is correct
17 Correct 260 ms 41668 KB Output is correct
18 Incorrect 414 ms 41044 KB Output isn't correct
19 Halted 0 ms 0 KB -