oj.uz

Submission #787546

# Submission time Handle Problem Language Result Execution time Memory
787546 2023-07-19T09:29:15 Z doowey Measures (CEOI22_measures) C++17
0 / 100
 136 ms 24160 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 40;

vector<pii> P;
vector<ll> p;

bool A[N];

ll D;

struct Node{
    ll res;
    ll i_val;
    ll j_val;
    ll lazy;
};

Node T[N * 4 + 100];

Node unite(Node A, Node B){
    Node nw;
    nw.res = max(A.res, B.res);
    nw.i_val = max(A.i_val, B.i_val);
    nw.j_val = max(A.j_val, B.j_val);
    nw.res = max(nw.res, B.i_val + A.j_val);
    nw.lazy = 0ll;
    return nw;
}

const ll inf = (ll)1e18;

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].i_val = -inf;
        T[node].j_val = -inf;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node]=unite(T[node*2],T[node*2+1]);
}

void push(int node, int cl, int cr){
    if(T[node].lazy == 0) return;
    T[node].i_val += D * 1ll * T[node].lazy;
    T[node].j_val -= D * 1ll * T[node].lazy;
    if(cl != cr){
        T[node*2+1].lazy += T[node].lazy;
        T[node*2].lazy += T[node].lazy;
    }
    T[node].lazy = 0;
}



void set_pos(int node, int cl, int cr, int id){
    push(node, cl, cr);
    if(cl == cr){
        T[node].i_val += inf-P[id].fi+D;
        T[node].j_val += inf+P[id].fi-D;
        T[node].res = 0ll;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        set_pos(node * 2, cl, mid, id);
    else
        set_pos(node * 2 + 1, mid + 1, cr, id);
    T[node] = unite(T[node*2],T[node*2+1]);
}

void inc(int node, int cl, int cr, int tl, int tr, int v){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    inc(node * 2, cl, mid, tl, tr, v);
    inc(node * 2 + 1, mid + 1, cr, tl, tr, v);
    T[node]=unite(T[node*2],T[node*2+1]);
}

int get_val(int node, int cl, int cr, int id, int m){
    push(node, cl, cr);
    if(cl==cr){
        if(m == 0)
            return T[node].i_val;
        else
            return T[node].j_val;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        return get_val(node * 2, cl, mid, id, m);
    else
        return get_val(node * 2 + 1, mid + 1, cr, id, m);
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n, m;
    cin >> n >> m >> D;
    p.resize(n + m);
    for(int i = 0 ; i < n; i ++ ){
        cin >> p[i];
    }
    for(int i = n ; i < n + m; i ++ ){
        cin >> p[i];
    }
    for(int i = 0 ; i < n + m ; i ++) {
        P.push_back(mp(p[i], i));
    }
    sort(P.begin(), P.end());
    build(1, 0, n + m - 1);
    int id;
    ll oo;
    for(int i = 0 ; i < n + m ; i ++ ){
        id = lower_bound(P.begin(), P.end(), mp(p[i], i)) - P.begin();
        set_pos(1, 0, n + m - 1, id);
        inc(1, 0, n + m - 1, id + 1, n + m - 1, +1);

        if(i >= n){
            oo = T[1].i_val + T[1].j_val;
            cout << oo / 2ll;
            if(oo % 2 != 0) cout << ".5 ";
            else cout << " ";
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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