oj.uz

Submission #865820

# Submission time Handle Problem Language Result Execution time Memory
865820 2023-10-24T18:49:30 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 416 ms 43588 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 = 0; i < m; ++i){
    ll x; cin >> x;
    v.pb({x, i});
  }
  sort(all(v));
  for(int i = 0; i < m; ++i) pos[i] = v[i][1];
  set<int> active;
  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;
    auto it = active.lower_bound(P);
   
    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);

    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 'void solve()':
Main.cpp:108:10: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  108 |     auto it = active.lower_bound(P);
      |          ^~
Main.cpp: In function 'int main()':
Main.cpp:131:15: warning: unused variable 'aa' [-Wunused-variable]
  131 |   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 249 ms 40636 KB Output is correct
2 Correct 252 ms 42684 KB Output is correct
3 Correct 257 ms 42688 KB Output is correct
4 Correct 256 ms 41136 KB Output is correct
5 Correct 250 ms 42436 KB Output is correct
6 Correct 248 ms 41332 KB Output is correct
7 Correct 251 ms 42020 KB Output is correct
8 Correct 257 ms 40636 KB Output is correct
9 Correct 260 ms 40416 KB Output is correct
10 Correct 252 ms 43588 KB Output is correct
11 Correct 259 ms 41616 KB Output is correct
12 Correct 253 ms 42292 KB Output is correct
13 Correct 250 ms 41140 KB Output is correct
14 Correct 250 ms 42472 KB Output is correct
15 Correct 250 ms 42172 KB Output is correct
16 Correct 255 ms 40768 KB Output is correct
17 Correct 248 ms 41852 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 40636 KB Output is correct
2 Correct 252 ms 42684 KB Output is correct
3 Correct 257 ms 42688 KB Output is correct
4 Correct 256 ms 41136 KB Output is correct
5 Correct 250 ms 42436 KB Output is correct
6 Correct 248 ms 41332 KB Output is correct
7 Correct 251 ms 42020 KB Output is correct
8 Correct 257 ms 40636 KB Output is correct
9 Correct 260 ms 40416 KB Output is correct
10 Correct 252 ms 43588 KB Output is correct
11 Correct 259 ms 41616 KB Output is correct
12 Correct 253 ms 42292 KB Output is correct
13 Correct 250 ms 41140 KB Output is correct
14 Correct 250 ms 42472 KB Output is correct
15 Correct 250 ms 42172 KB Output is correct
16 Correct 255 ms 40768 KB Output is correct
17 Correct 248 ms 41852 KB Output is correct
18 Incorrect 416 ms 41516 KB Output isn't correct
19 Halted 0 ms 0 KB -