Submission #809236

#	Time	Username	Problem	Language	Result	Execution time	Memory
809236		HaroldVemeno	Measures (CEOI22_measures)	C++17	0 / 100	86 ms	12616 KiB

Main

#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using pii = pair<int, int>;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int n, m, d;

struct Node {
    int v;
    int p;
    int ss;
    ll lm;
    ll rm;
    ll time;
    Node* l;
    Node* r;
};

int size(Node* a) {
    return a?a->ss:0;
}

Node* pull(Node* a) {
    if(!a) return a;
    int ls = size(a->l);
    int rs = size(a->r);
    D(a->v);
    a->ss = 1+ls+rs;
    a->time = 0;
    a->rm = a->v + rs*d;
    a->lm = a->v - ls*d;
    ll mv = a->v + d*size(a->l);
    if(a->r) {
        a->time = max(a->time, a->r->time);
        a->time = max(a->time, d-(a->r->lm - a->v));
        a->rm = max(a->rm, a->r->rm);
        a->lm = min(a->lm, a->r->lm - (ls+1)*d);
    }
    if(a->l) {
        a->time = max(a->time, a->l->time);
        a->time = max(a->time, d-(a->v - a->l->rm));
        a->lm = min(a->lm, a->l->lm);
        a->rm = max(a->rm, a->l->rm + (rs+1)*d);
    }
    if(a->l && a->r) {
        a->time = max(a->time, d-(a->r->lm - a->l->rm));
    }
    return a;
}

Node* concat(Node* l, Node* r) {
    if(!l) return r;
    if(!r) return l;
    if(l->p > r->p) {
        l->r = concat(l->r, r);
        pull(l);
        return l;
    } else {
        r->l = concat(l, r->l);
        pull(r);
        return r;
    }
}

pair<Node*, Node*> split(Node* a, ll v) {
    if(!a) return {a, a};
    if(a->v < v) {
        auto[l, r] = split(a->r, v);
        a->r = l;
        pull(a);
        return {a, r};
    } else {
        auto[l, r] = split(a->l, v);
        a->l = r;
        pull(a);
        return {l, a};
    }
}

void solve() {
    cin >> n >> m >> d;
    srand(48364);
    vector<Node> buf(n+m);
    for(int i = 0; i < n; ++i) {
        cin >> buf[i].v;
        buf[i].p = rand();
        pull(&buf[i]);
    }
    for(int i = 0; i < m; ++i) {
        cin >> buf[n+i].v;
        buf[n+i].p = rand();
        pull(&buf[n+i]);
    }

    Node* tr = nullptr;
    for(int i = 0; i < n; ++i) {
        auto [l, r] = split(tr, buf[i].v);
        tr = concat(l, concat(&buf[i], r));
        D(tr->ss);
    }
    for(int i = n;  i < n+m; ++i) {
        auto [l, r] = split(tr, buf[i].v);
        tr = concat(l, concat(&buf[i], r));
        D(tr->ss);
        D(tr->rm);
        D(tr->lm);
        cout << tr->time/2;
        if(tr->time&1) cout << ".5";
        cout << ' ';
    }
    cout << '\n';

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed;

    solve();
}

Compilation message (stderr)

Main.cpp: In function 'Node* pull(Node*)':
Main.cpp:45:8: warning: unused variable 'mv' [-Wunused-variable]
   45 |     ll mv = a->v + d*size(a->l);
      |        ^~

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