Submission #633626

#	Time	Username	Problem	Language	Result	Execution time	Memory
633626		Ooops_sorry	Measures (CEOI22_measures)	C++14	0 / 100	1565 ms	22096 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int N = 4e5 + 10;
int n, m, d;

struct Fenwick {
    vector<ll> t;
    Fenwick(int n) {
        t.resize(n);
    }
    void inc(int i, int d) {
        for (; i < t.size(); i = (i | (i + 1))) {
            t[i] += d;
        }
    }
    ll get(int r) {
        ll ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += t[r];
        }
        return ans;
    }
    ll get(ll l, ll r) {
        return get(r) - get(l - 1);
    }
} pr(N), sf(N);

struct SegTree {
    vector<int> t;
    SegTree(int n) {
        t.resize(4 * n);
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            t[v] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) {
            update(2 * v, l, m, pos, val);
        } else {
            update(2 * v + 1, m + 1, r, pos, val);
        }
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    int get_ind(int v, int l, int r, int val) {
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        if (t[v * 2] >= val) {
            return get_ind(2 * v, l, m, val);
        } else {
            return get_ind(2 * v + 1, m + 1, r, val - t[v * 2]);
        }
    }
} t(N);

set<pair<int,int>> st;
vector<pair<int,int>> u;

void update_pr(auto it, int x) {
    if (it == st.begin()) return;
    auto pre = prev(it);
    int pos = lower_bound(u.begin(), u.end(), *it) - u.begin();
    pr.inc(pos, x * max(0, d - (it->first - pre->first)));
}

void update_sf(auto it, int x) {
    if (next(it) == st.end()) return;
    auto nxt = next(it);
    int pos = lower_bound(u.begin(), u.end(), *it) - u.begin();
    sf.inc(pos, x * max(0, d - (nxt->first - it->first)));
}

ld get_val(int num) {
    int pos = t.get_ind(1, 0, N - 1, num);
    return (ld)max(pr.get(0, pos), sf.get(pos, N - 1));
}

ld get_pair_val(int num) {
    int pos1 = t.get_ind(1, 0, N - 1, num), pos2 = t.get_ind(1, 0, N - 1, num + 1);
    return (ld)max(pr.get(0, pos1), sf.get(pos2, N - 1)) + (ld)max(0, d - (u[pos2].first - u[pos1].first)) / 2.0;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int cnt = 0, kol = 0;
    cin >> n >> m >> d;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        u.pb({a[i], kol});
        st.insert({a[i], kol++});
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        u.pb({b[i], kol++});
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    int sz = u.size();
    for (auto it = st.begin(); it != st.end(); it = next(it)) {
        update_pr(it, 1);
        update_sf(it, 1);
    }
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(u.begin(), u.end(), make_pair(a[i], cnt)) - u.begin();
        t.update(1, 0, N - 1, pos, 1);
        cnt++;
    }
    for (int i = 0; i < m; i++) {
        auto up = st.upper_bound({b[i], cnt});
        if (up != st.end() && up != st.begin()) {
            update_pr(up, -1);
            update_sf(prev(up), -1);
        }
        st.insert({b[i], cnt});
        auto it = st.lower_bound({b[i], cnt});
        update_pr(it, 1);
        update_sf(it, 1);
        if (next(it) != st.end()) {
            update_pr(next(it), 1);
        }
        if (it != st.begin()) {
            update_sf(prev(it), 1);
        }
        int pos = lower_bound(u.begin(), u.end(), make_pair(b[i], cnt)) - u.begin();
        t.update(1, 0, N - 1, pos, 1);
        ld ans = 1e18;
        int l = 0, r = st.size();
        while (r - l > 2) {
            int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
            if (get_val(m1) > get_val(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        for (auto a : {l, l + 1, l + 2}) {
            if (1 <= a && a <= st.size()) {
                ans = min(ans, get_val(a));
            }
        }
        l = 0, r = st.size();
        while (r - l > 2) {
            int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
            if (get_pair_val(m1) > get_pair_val(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        for (auto a : {l, l + 1, l + 2}) {
            if (1 <= a && a + 1 <= st.size()) {
                ans = min(ans, get_pair_val(a));
            }
        }
        cout << ans << ' ';
        cnt++;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Fenwick::inc(int, int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (; i < t.size(); i = (i | (i + 1))) {
      |                ~~^~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:70:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   70 | void update_pr(auto it, int x) {
      |                ^~~~
Main.cpp:77:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   77 | void update_sf(auto it, int x) {
      |                ^~~~
Main.cpp: In function 'int main()':
Main.cpp:153:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             if (1 <= a && a <= st.size()) {
      |                           ~~^~~~~~~~~~~~
Main.cpp:167:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |             if (1 <= a && a + 1 <= st.size()) {
      |                           ~~~~~~^~~~~~~~~~~~
Main.cpp:114:9: warning: unused variable 'sz' [-Wunused-variable]
  114 |     int sz = u.size();
      |         ^~

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