제출 #1305707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305707		loom	Measures (CEOI22_measures)	C++20	0 / 100	170 ms	28816 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define _ <<' '<<
#define nl '\n'

const int N = 3e5;
int mn[4*N], mx[4*N], cnt[4*N], lz[4*N];
int d;

void lazy(int l, int r, int p){
   mn[p] += lz[p];
   mx[p] += lz[p];

   if(l != r){
      lz[p*2] += lz[p];
      lz[p*2+1] += lz[p];
   }

   lz[p] = 0;
}

void upd(int l, int r, int p, int ql, int qr){
   if(r < ql or qr < l) return;
   if(ql <= l and r <= qr){
      lz[p] += d;
      return;
   }

   int m = (l+r)/2;
   upd(l, m, p*2, ql, qr);
   upd(m+1, r, p*2+1, ql, qr);

   mx[p] = max(mx[p*2], mx[p*2+1]);
   mn[p] = min(mn[p*2], mn[p*2+1]);
}

void add(int l, int r, int p, int q, int v, int i){
   lazy(l, r, p);
   if(l == r){
      cnt[p] = 1;
      mn[p] = mx[p] = d * i - v;
      return;
   }

   int m = (l+r)/2;
   if(q <= m) add(l, m, p*2, q, v, i);
   else add(m+1, r, p*2+1, q, v, i + cnt[p*2]);

   cnt[p] = cnt[p*2] + cnt[p*2+1];
   mx[p] = max(mx[p*2], mx[p*2+1]);
   mn[p] = min(mn[p*2], mn[p*2+1]);
}

int qmn(int l, int r, int p, int ql, int qr){
   lazy(l, r, p);
   if(r < ql or qr < l) return inf;
   if(ql <= l and r <= qr) return mn[p];

   int m = (l+r)/2;
   return min(qmn(l, m, p*2, ql, qr), qmn(m+1, r, p*2+1, ql, qr));
}

int qmx(int l, int r, int p, int ql, int qr){
   lazy(l, r, p);
   if(r < ql or qr < l) return -inf;
   if(ql <= l and r <= qr) return mx[p];

   int m = (l+r)/2;
   return max(qmx(l, m, p*2, ql, qr), qmx(m+1, r, p*2+1, ql, qr));
}

void solve(){
   int m, n;
   cin>>m>>n>>d;
   n += m;

   int a[n];
   for(int i = 0; i < n; i++) cin>>a[i];

   vector<int> v(n);
   iota(v.begin(), v.end(), 0);

   sort(v.begin(), v.end(), [&](int i, int j){
      return a[i] < a[j];
   });

   int ix[n];
   for(int i = 0; i < n; i++) ix[v[i]] = i;

   for(int i = 0; i < 4*n; i++) mn[i] = inf, mx[i] = -inf;
   int ans = 0;

   for(int i = 0; i < n; i++){
      add(0, n, 1, ix[i], a[i], 0);
      upd(0, n, 1, ix[i] + 1, n);

      ans = max(ans, qmx(0, n, 1, ix[i], n) - qmn(0, n, 1, 0, ix[i]));
      if(i < m) continue;

      cout<<ans/2<<(ans % 2 ? ".5 " : " ");
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41