Submission #865821

#	Time	Username	Problem	Language	Result	Execution time	Memory
865821		mychecksedad	Measures (CEOI22_measures)	C++17	35 / 100	299 ms	34288 KiB

Main

/* 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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41