oj.uz

Submission #997485

# Submission time Handle Problem Language Result Execution time Memory
997485 2024-06-12T11:29:21 Z crafticat Measures (CEOI22_measures) C++17
35 / 100
 438 ms 16060 KB 
#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.upper_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;
        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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 13888 KB Output is correct
2 Correct 379 ms 15700 KB Output is correct
3 Correct 395 ms 15700 KB Output is correct
4 Correct 365 ms 13652 KB Output is correct
5 Correct 388 ms 14928 KB Output is correct
6 Correct 386 ms 14088 KB Output is correct
7 Correct 396 ms 14928 KB Output is correct
8 Correct 385 ms 13648 KB Output is correct
9 Correct 384 ms 13552 KB Output is correct
10 Correct 378 ms 16060 KB Output is correct
11 Correct 339 ms 14416 KB Output is correct
12 Correct 409 ms 15440 KB Output is correct
13 Correct 383 ms 13648 KB Output is correct
14 Correct 403 ms 15696 KB Output is correct
15 Correct 438 ms 15436 KB Output is correct
16 Correct 374 ms 13696 KB Output is correct
17 Correct 410 ms 15052 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 13888 KB Output is correct
2 Correct 379 ms 15700 KB Output is correct
3 Correct 395 ms 15700 KB Output is correct
4 Correct 365 ms 13652 KB Output is correct
5 Correct 388 ms 14928 KB Output is correct
6 Correct 386 ms 14088 KB Output is correct
7 Correct 396 ms 14928 KB Output is correct
8 Correct 385 ms 13648 KB Output is correct
9 Correct 384 ms 13552 KB Output is correct
10 Correct 378 ms 16060 KB Output is correct
11 Correct 339 ms 14416 KB Output is correct
12 Correct 409 ms 15440 KB Output is correct
13 Correct 383 ms 13648 KB Output is correct
14 Correct 403 ms 15696 KB Output is correct
15 Correct 438 ms 15436 KB Output is correct
16 Correct 374 ms 13696 KB Output is correct
17 Correct 410 ms 15052 KB Output is correct
18 Incorrect 421 ms 15048 KB Output isn't correct
19 Halted 0 ms 0 KB -