제출 #787519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787519		doowey	Measures (CEOI22_measures)	C++17	35 / 100	223 ms	26616 KiB

Main

#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;

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;
        T[node].j_val += inf+P[id].fi;
        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 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;
    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, n + m - 1, +1);
        if(i >= n){
            cout << T[1].res / 2ll;
            if(T[1].res % 2 != 0) cout << ".5 ";
            else cout << " ";
        }
    }
    return 0;
}

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