oj.uz

Submission #677524

# Submission time Handle Problem Language Result Execution time Memory
677524 2023-01-03T13:59:23 Z stanislavpolyn Measures (CEOI22_measures) C++17
59 / 100
 1500 ms 6512 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 4e5 + 5;

int n, m;
ll D;
ll a[N];
ll b[N];
ll d[N];
ll suff[N];

int rnd(int l, int r) {
    return rng() % (r - l + 1) + l;
}

ll T[N];

ve<ll> Q;

ve<pll> u;
//bool subtask = 1;

//ve<ll> v;
//ve<ll> pos;

//void add(ll x) {
//    assert(is_sorted(all(v)));
//    int idx = sz(v) - 1;
//    fr (i, 0, sz(v) - 1) {
//        if (x > v[i]) {
//            idx = i - 1;
//            break;
//        }
//    }
//
//    ll myPos = -1;
//    if (idx - 1 >= 0) {
//        myPos = max(x, pos[idx - 1] + D);
//    } else {
//        myPos = x;
//    }
//}
int id[N];

struct Node {
    ll last;
    ll ans;
};

Node t[4 * N];

//void build(int v, int tl, int tr) {
//    t[v] = {-1e18, -1e18};
//    if (tl == tr) {
//        return;
//    }
//    int tm = (tl + tr) >> 1;
//    build(v << 1, tl, tm);
//    build(v << 1 | 1, tm + 1, tr);
//}
//
//void upd(int v, int tl, int tr, int pos) {
//    if (tl == tr) {
//
//        return;
//    }
//}

bool subtask = 1;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m >> D;

    D *= 2;

    fr (i, 1, n) {
        cin >> a[i];
//        a[i] = rnd(1, int(100));
        a[i] *= 2;
    }

    fr (i, 1, m) {
        cin >> b[i];
        if (i > 1) {
            subtask &= b[i] >= b[i - 1];
        }
    }
    subtask &= n == 0;

    if (!subtask) {
        fr (i, 1, m) {
            ll x;
            x = b[i];
            x *= 2;

            a[++n] = x;
            sort(a + 1, a + 1 + n);

            ll last = a[1];
            ll ans = 0;
            fr (j, 2, n) {
                if (a[j] - last >= D) {
                    last = a[j];
                    continue;
                }
                umx(ans, abs(a[j] - (last + D)));
                last += D;
            }
            ans /= 2;

            cout << ans / 2;
            if (ans % 2) cout << ".5";
            cout << "\n";
        }

    } else {
//        cout << "YES\n";
        ll last = -1;
        ll ans = 0;
        fr (i, 1, m) {
            ll x;
            x = b[i];
            x *= 2;
            n++;

            if (n == 1) {
                last = x;
            } else {
                if (x - last >= D) {
                    last = x;
                } else {
                    umx(ans, abs(x - (last + D)));
                    last += D;
                }
            }
//            cout << "ans: " << ans << "\n";

            cout << ans / 4;
            if ((ans / 2) % 2) cout << ".5";
            cout << "\n";
        }
    }


//    fr (i, 1, m) {
//        ll x;
//        cin >> x;
//        x *= 2;
//        Q.pb(x);
//        u.pb({x, i});
//    }
//
//    sort(all(u));
//    fr (i, 0, sz(u) - 1) {
//        id[u[i].se] = i;
//    }
//


    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 108 ms 1900 KB Output is correct
10 Correct 156 ms 1900 KB Output is correct
11 Correct 38 ms 1868 KB Output is correct
12 Correct 157 ms 1808 KB Output is correct
13 Correct 51 ms 1876 KB Output is correct
14 Correct 102 ms 1900 KB Output is correct
15 Correct 95 ms 1876 KB Output is correct
16 Correct 53 ms 1912 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2900 KB Output is correct
2 Correct 39 ms 6512 KB Output is correct
3 Correct 38 ms 6508 KB Output is correct
4 Correct 32 ms 4060 KB Output is correct
5 Correct 35 ms 5568 KB Output is correct
6 Correct 35 ms 4532 KB Output is correct
7 Correct 37 ms 5760 KB Output is correct
8 Correct 35 ms 4632 KB Output is correct
9 Correct 36 ms 4132 KB Output is correct
10 Correct 38 ms 6468 KB Output is correct
11 Correct 36 ms 4936 KB Output is correct
12 Correct 37 ms 6096 KB Output is correct
13 Correct 33 ms 4284 KB Output is correct
14 Correct 36 ms 6168 KB Output is correct
15 Correct 39 ms 6172 KB Output is correct
16 Correct 32 ms 4020 KB Output is correct
17 Correct 36 ms 5404 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2900 KB Output is correct
2 Correct 39 ms 6512 KB Output is correct
3 Correct 38 ms 6508 KB Output is correct
4 Correct 32 ms 4060 KB Output is correct
5 Correct 35 ms 5568 KB Output is correct
6 Correct 35 ms 4532 KB Output is correct
7 Correct 37 ms 5760 KB Output is correct
8 Correct 35 ms 4632 KB Output is correct
9 Correct 36 ms 4132 KB Output is correct
10 Correct 38 ms 6468 KB Output is correct
11 Correct 36 ms 4936 KB Output is correct
12 Correct 37 ms 6096 KB Output is correct
13 Correct 33 ms 4284 KB Output is correct
14 Correct 36 ms 6168 KB Output is correct
15 Correct 39 ms 6172 KB Output is correct
16 Correct 32 ms 4020 KB Output is correct
17 Correct 36 ms 5404 KB Output is correct
18 Execution timed out 1570 ms 3932 KB Time limit exceeded
19 Halted 0 ms 0 KB -