oj.uz

Submission #678465

# Submission time Handle Problem Language Result Execution time Memory
678465 2023-01-06T04:23:41 Z cig32 Measures (CEOI22_measures) C++17
100 / 100
 414 ms 52104 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }

struct segtree_mss {
  struct node {
    int premax = 0;
    int sufmax = 0;
    int totmax = 0;
    int sum = 0;
  };
  vector<node> st;
  int stok;
  void push_up(int idx) {
    st[idx].premax = max(st[2*idx+1].premax, st[2*idx+1].sum + st[2*idx+2].premax);
    st[idx].sufmax = max(st[2*idx+2].sufmax, st[2*idx+2].sum + st[2*idx+1].sufmax);
    st[idx].totmax = max({
      st[2*idx+1].totmax,
      st[2*idx+2].totmax,
      st[2*idx+1].sufmax + st[2*idx+2].premax
    });
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
  }
  void u(int l, int r, int tar, int idx, int val) {
    if(l == r) {
      st[idx].sum = val;
      st[idx].premax = max(val, 0ll);
      st[idx].sufmax = max(val, 0ll);
      st[idx].totmax = max(val, 0ll);
      return;
    }
    int mid = (l + r) >> 1;
    if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
    else u(mid+1, r, tar, 2*idx+2, val);
    push_up(idx);
  }
  public:
  void resize(int k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void point_assign(int i, int v) {
    u(1, stok, i, 0, v);
  }
  int query_mss() {
    return st[0].totmax;
  }
};

void solve(int tc) {
  int n, m, d;
  cin >> n >> m >> d;
  if(n > 0) {
    vector<int> v;
    for(int i=1; i<=n+m; i++) {
      int x;
      cin >> x;
      v.push_back(x);
      if(i <= n) continue;
      sort(v.begin(), v.end());
      int lb = 0, rb = 1e15;
      while(lb < rb) {
        double mid = (lb + rb) * 0.25;
        double mind = v[0] - mid;
        bool ok = 1;
        for(int i=1; i<v.size(); i++) {
          double res = v[i] - mid;
          double new_mind = max(mind + d, res);
          if(new_mind - mind < d || abs(new_mind - v[i]) > mid) {
            ok = 0; break;
          }
          mind = new_mind;
        }
        int realmid = (lb + rb) / 2;
        if(ok) rb = realmid;
        else lb = realmid + 1;
      }
      if(lb & 1) cout << lb / 2 << ".5" << " \n"[i == n+m];
      else cout << lb / 2 << " \n"[i == n+m];
    }
    return;
  }
  int dp[m+1];
  dp[0] = 0;
  int w[m+1], v[m+1];
  pair<int, int> ww[m+1];
  int pos[m+1];
  for(int i=1; i<=m; i++) {
    cin >> w[i];
    ww[i].first = w[i];
    ww[i].second = i;
  }
  sort(ww+1, ww+1+m);
  for(int i=1; i<=m; i++) pos[ww[i].second] = i;
  v[1] = 0;
  for(int i=2; i<=m; i++) v[i] = d - (w[i] - w[i-1]);
  segtree_mss stm;
  stm.resize(m);
  set<pair<int, int> > st;
  st.insert({4e9, -1});
  st.insert({-4e9, -1});
  for(int i=1; i<=m; i++) {
    if(st.empty()) {
      st.insert({w[i], i});
      cout << 0 << " \n"[i == m];
      continue;
    }
    auto it = st.lower_bound({w[i], i});
    if((*it).second != -1) {
      int ptr = (*it).second;
      stm.point_assign(pos[ptr], d - ((*it).first - w[i]));
    }
    it--;
    if((*it).second != -1) {
      stm.point_assign(pos[i], d - (w[i] - (*it).first));
    }
    else {
      stm.point_assign(pos[i], 0);
    }
    st.insert({w[i], i});
    int ans = stm.query_mss();
    cout << ans / 2 << (ans & 1 ? ".5" : "") << " \n"[i == m];
  }
}

int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
>= 0 required
> 2*t: sad

bounding trick? (IOI 2021 candies)
1) point update the array
2) compute the answer given t

-> given many queries
Type 1: (x[i] < 0)  a[i]:=max(0, a[i]-x[i])
Type 2: (x[i] >= 0) a[i]:=a[i]+x[i], if a[i] > 2*t then SAD

Basically -> max subarray sum > 2*t: SAD else NOT SAD
*/

Compilation message

Main.cpp: In function 'void solve(long long int)':
Main.cpp:85:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=1; i<v.size(); i++) {
      |                      ~^~~~~~~~~
Main.cpp:102:7: warning: variable 'dp' set but not used [-Wunused-but-set-variable]
  102 |   int dp[m+1];
      |       ^~
Main.cpp:104:15: warning: variable 'v' set but not used [-Wunused-but-set-variable]
  104 |   int w[m+1], v[m+1];
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 356 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 4 ms 356 KB Output is correct
9 Correct 326 ms 2632 KB Output is correct
10 Correct 342 ms 2632 KB Output is correct
11 Correct 249 ms 2760 KB Output is correct
12 Correct 370 ms 2732 KB Output is correct
13 Correct 232 ms 2768 KB Output is correct
14 Correct 318 ms 2760 KB Output is correct
15 Correct 306 ms 2764 KB Output is correct
16 Correct 236 ms 2760 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 48540 KB Output is correct
2 Correct 174 ms 50428 KB Output is correct
3 Correct 177 ms 51912 KB Output is correct
4 Correct 165 ms 49456 KB Output is correct
5 Correct 168 ms 50924 KB Output is correct
6 Correct 175 ms 49904 KB Output is correct
7 Correct 170 ms 51156 KB Output is correct
8 Correct 170 ms 50000 KB Output is correct
9 Correct 192 ms 49496 KB Output is correct
10 Correct 182 ms 51884 KB Output is correct
11 Correct 167 ms 50228 KB Output is correct
12 Correct 171 ms 51552 KB Output is correct
13 Correct 166 ms 49696 KB Output is correct
14 Correct 167 ms 51564 KB Output is correct
15 Correct 172 ms 51504 KB Output is correct
16 Correct 160 ms 49496 KB Output is correct
17 Correct 183 ms 50924 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 48540 KB Output is correct
2 Correct 174 ms 50428 KB Output is correct
3 Correct 177 ms 51912 KB Output is correct
4 Correct 165 ms 49456 KB Output is correct
5 Correct 168 ms 50924 KB Output is correct
6 Correct 175 ms 49904 KB Output is correct
7 Correct 170 ms 51156 KB Output is correct
8 Correct 170 ms 50000 KB Output is correct
9 Correct 192 ms 49496 KB Output is correct
10 Correct 182 ms 51884 KB Output is correct
11 Correct 167 ms 50228 KB Output is correct
12 Correct 171 ms 51552 KB Output is correct
13 Correct 166 ms 49696 KB Output is correct
14 Correct 167 ms 51564 KB Output is correct
15 Correct 172 ms 51504 KB Output is correct
16 Correct 160 ms 49496 KB Output is correct
17 Correct 183 ms 50924 KB Output is correct
18 Correct 376 ms 50348 KB Output is correct
19 Correct 414 ms 51604 KB Output is correct
20 Correct 182 ms 52104 KB Output is correct
21 Correct 225 ms 49808 KB Output is correct
22 Correct 303 ms 50268 KB Output is correct
23 Correct 197 ms 50188 KB Output is correct
24 Correct 380 ms 50328 KB Output is correct
25 Correct 165 ms 49872 KB Output is correct
26 Correct 364 ms 49552 KB Output is correct
27 Correct 369 ms 51644 KB Output is correct
28 Correct 317 ms 50248 KB Output is correct
29 Correct 341 ms 50268 KB Output is correct
30 Correct 211 ms 49100 KB Output is correct
31 Correct 209 ms 51660 KB Output is correct
32 Correct 221 ms 50580 KB Output is correct
33 Correct 374 ms 48264 KB Output is correct
34 Correct 209 ms 50444 KB Output is correct