oj.uz

Submission #865821

# Submission time Handle Problem Language Result Execution time Memory
865821 2023-10-24T18:52:21 Z mychecksedad Measures (CEOI22_measures) C++17
35 / 100
 299 ms 34288 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[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);

    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 'int main()':
Main.cpp:128:15: warning: unused variable 'aa' [-Wunused-variable]
  128 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 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 8536 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 213 ms 31680 KB Output is correct
2 Correct 217 ms 33284 KB Output is correct
3 Correct 231 ms 34288 KB Output is correct
4 Correct 217 ms 31164 KB Output is correct
5 Correct 214 ms 33064 KB Output is correct
6 Correct 213 ms 31680 KB Output is correct
7 Correct 219 ms 32956 KB Output is correct
8 Correct 219 ms 31420 KB Output is correct
9 Correct 212 ms 31112 KB Output is correct
10 Correct 219 ms 33696 KB Output is correct
11 Correct 222 ms 32204 KB Output is correct
12 Correct 214 ms 33720 KB Output is correct
13 Correct 213 ms 31148 KB Output is correct
14 Correct 216 ms 33252 KB Output is correct
15 Correct 220 ms 32960 KB Output is correct
16 Correct 218 ms 31420 KB Output is correct
17 Correct 214 ms 32960 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 31680 KB Output is correct
2 Correct 217 ms 33284 KB Output is correct
3 Correct 231 ms 34288 KB Output is correct
4 Correct 217 ms 31164 KB Output is correct
5 Correct 214 ms 33064 KB Output is correct
6 Correct 213 ms 31680 KB Output is correct
7 Correct 219 ms 32956 KB Output is correct
8 Correct 219 ms 31420 KB Output is correct
9 Correct 212 ms 31112 KB Output is correct
10 Correct 219 ms 33696 KB Output is correct
11 Correct 222 ms 32204 KB Output is correct
12 Correct 214 ms 33720 KB Output is correct
13 Correct 213 ms 31148 KB Output is correct
14 Correct 216 ms 33252 KB Output is correct
15 Correct 220 ms 32960 KB Output is correct
16 Correct 218 ms 31420 KB Output is correct
17 Correct 214 ms 32960 KB Output is correct
18 Incorrect 299 ms 31676 KB Output isn't correct
19 Halted 0 ms 0 KB -