제출 #691475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691475		fatemetmhr	Measures (CEOI22_measures)	C++17	0 / 100	140 ms	42320 KiB

Main

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 20;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

ll d, x[maxn5];
int per[maxn5], pos[maxn5];

struct corona{
    bool empty;
    ll max_time, last_pos, first_pos;
    corona(){
        empty = true;
    }
} seg[maxnt];

corona operator +(corona a, corona b){
    if(a.empty)
        return b;
    if(b.empty)
        return a;
    corona ans;
    ans.empty = false;
    ll shifta = 0, shiftb = 0;
    if(d <= b.first_pos - a.last_pos){
        ll can = b.first_pos - a.last_pos - d;
        if(a.max_time < b.max_time)
            shifta = min(can, b.max_time - a.max_time);
        if(b.max_time < a.max_time)
            shiftb = min(can, a.max_time - b.max_time) * -1;
    }
    else{
        ll need = d - (b.first_pos - a.last_pos);
        if(a.max_time < b.max_time){
            shifta = min(need, b.max_time - a.max_time);
            shifta *= -1;
            need += shifta;
        }
        if(a.max_time > b.max_time){
            shiftb = min(need, a.max_time - b.max_time);
            need -= shiftb;
        }
        need /= 2;
        shifta -= need;
        shiftb += need;
    }
    //cout << "look " << a.max_time << ' ' << a.first_pos << ' ' << a.last_pos << endl;
    //cout << b.max_time << ' ' << b.first_pos << ' ' << b.last_pos << endl;
    //cout << "ok " << shifta << ' ' << shiftb << ' ' << endl;
    ans.max_time = max(a.max_time + abs(shifta), b.max_time + abs(shiftb));
    ans.last_pos = b.last_pos + shiftb;
    ans.first_pos = a.first_pos + shifta;
    return ans;
}

inline bool cmp(int i, int j){return x[i] < x[j];}

void add(int l, int r, int id, int v){
    if(r - l == 1){
        seg[v].empty = false;
        seg[v].max_time = 0;
        seg[v].last_pos = seg[v].first_pos = x[per[l]];
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid)
        add(l, mid, id, v * 2);
    else
        add(mid, r, id, v * 2 + 1);
    seg[v] = seg[v * 2] + seg[v * 2 + 1];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m >> d;
    d *= 2;
    for(int i = 0; i < n; i++){
        cin >> x[i];
        x[i] *= 2;
        per[i] = i;
    }
    for(int i = n; i < m + n; i++){
        cin >> x[i];
        x[i] *= 2;
        per[i] = i;
    }
    sort(per, per + n + m, cmp);
    for(int i = 0; i < n + m; i++)
        pos[per[i]] = i;
    for(int i = 0; i < n; i++)
        add(0, n + m, pos[i], 1);
    for(int i = 0; i < m; i++){
        add(0, n + m, pos[i + n], 1);
        cout << seg[1].max_time / 2;
        if(seg[1].max_time & 1)
            cout << ".5";
        cout << ' ';
    }
    cout << endl;
}

/*
0 3 2
1 3 2
*/

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