Submission #997484

#	Time	Username	Problem	Language	Result	Execution time	Memory
997484		crafticat	Measures (CEOI22_measures)	C++17	35 / 100	420 ms	17232 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll pres = 1e2;
constexpr ll inf = (1e18);
constexpr ll epsilon = 1;

ll d;
using pll = pair<ll, ll>;

set<pll> dat;

ll insert(ll x, ll cAns) {
    auto it = dat.lower_bound({x,inf});
    it--;
    auto [l, rl] = *it;
    it++;
    auto [r, rr] = *it;

    ll beg = cAns, end = inf;
    while (end > beg) {
        ll mid = beg + (end - beg) / 2;
        ll diff = mid - cAns;
        ll jump = (rl - diff + d) - x;
        if (mid == 1) {
            int stop = 25;
        }
        jump = max(jump, -mid);
        ll prev = x + jump;
        if ((rr + diff < prev + d) || jump > mid) {
            beg = mid + 1;
        } else {
            end = mid;
        }
    }
    ll mid = beg;
    ll diff = mid - cAns;
    ll jump = (rl - diff + d) - x;
    jump = max(jump, -mid);
    ll prev = x + jump;

    dat.insert({x,prev});
    return beg;
}

void printAns(ll ans) {
    cout << ans / pres;
    ans %= pres;
    if (ans != 0) cout << ".";
    ll mul = pres;
    while (ans != 0) {
        mul /= 10;
        cout << (ans / mul) % 10;
        ans %= mul;
    }
    cout << "\n";
}

int main() {
    ll n, m; cin >> n >> m >> d;
    dat.insert({-inf,-inf});
    dat.insert({inf,inf});


    ll ans = 0;
    d*=pres;
    for (ll i = 0; i < n; ++i) {
        ll x; cin >> x;
        x *= pres;
        ans = insert(x,ans);
    }


    for (ll i = 0; i < m; ++i) {
        ll x; cin >> x;
        x *= pres;
        ans = insert(x,ans);
        printAns(ans);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'll insert(ll, ll)':
Main.cpp:28:17: warning: unused variable 'stop' [-Wunused-variable]
   28 |             int stop = 25;
      |                 ^~~~

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