제출 #900542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900542		Shayan86	Measures (CEOI22_measures)	C++14	100 / 100	714 ms	44736 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

const ll N = 4e5 + 50;
const ll inf1 = 1e16 + 7;
const ll inf2 = 1e18 + 7;

ll n, m, D, arr[N], id[N];

vector<pll> vec;

set<int> alive, root;

int bit[N];

void add_cnt(int x, int y){
    for(; x <= n+m+1; x += x & (-x)) bit[x] += y;
}

int get_cnt(int x){
    ll out = 0;
    for(; x; x -= x & (-x)) out += bit[x];
    return out;
}

ll seg[N*4], lz[N*4];

void build(int l = 0, int r = n+m+2, int id = 1){
    if(l+1 == r){
        seg[id] = -inf2;
        if(l == 0 || l == n+m+1) seg[id] = 0;
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void quex(int id, ll x){
    if(seg[id] <= -inf2) return;
    seg[id] += x; lz[id] += x;
}

void relax(int id){
    quex(lid, lz[id]);
    quex(rid, lz[id]);
    lz[id] = 0;
}

void upd(int x, ll y, int l = 0, int r = n+m+2, int id = 1){
    if(l+1 == r){
        seg[id] = y; return;
    }

    relax(id);
    if(x < mid) upd(x, y, l, mid, lid);
    else upd(x, y, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void add(int ql, int qr, ll x, int l = 0, int r = n+m+2, int id = 1){
    if(ql <= l && r <= qr){
        quex(id, x); return;
    }
    if(qr <= l || r <= ql) return;

    relax(id);
    add(ql, qr, x, l, mid, lid);
    add(ql, qr, x, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

ll get(int ql, int qr, int l = 0, int r = n+m+2, int id = 1){
    if(ql <= l && r <= qr) return seg[id];
    if(qr <= l || r <= ql) return 0;
    relax(id);
    return max(get(ql, qr, l, mid, lid), get(ql, qr, mid, r, rid));
}

int main(){
    fast_io;

    cin >> n >> m >> D;

    arr[0] = -inf1; vec.pb({arr[0], 0});
    for(int i = 1; i <= n+m; i++){
        cin >> arr[i]; vec.pb({arr[i], i});
    }
    arr[n+m+1] = inf1; vec.pb({arr[n+m+1], n+m+1});

    sort(all(vec));
    for(int i = 1; i <= n+m; i++) id[vec[i].S] = i;

    root.insert(0); alive.insert(0);
    root.insert(n+m+1); alive.insert(n+m+1); add_cnt(n+m+1, 1);

    build();

    for(int i = 1; i <= n+m; i++){
        auto itr = alive.lower_bound(id[i]);
        itr--; int x = *itr;

        ll th = max(0ll, get(x, x+1) + D + vec[x].F - arr[i]);
        upd(id[i], th); alive.insert(id[i]); root.insert(id[i]); add_cnt(id[i], 1);

        itr = root.upper_bound(id[i]);
        if(id[i]+1 < *itr) add(id[i]+1, *itr, (get(id[i], id[i]+1) + arr[i]) - (get(x, x+1) + vec[x].F));

        while(true){
            int y = *itr;
            th = max(0ll, (get(id[i], id[i]+1) + arr[i]) + D * (get_cnt(y) - get_cnt(id[i])) - (get(y, y+1) + vec[y].F));
            if(!th) break;
            root.erase(y);
            itr = root.lower_bound(y); add(y, *itr, th);
        }

        if(i > n){
            ll out = get(0, n+m+2);
            ll o1 = out / 2; ll o2 = out % 2;
            cout << o1;
            if(o2) cout << ".5";
            cout << sep;
        }
    }

}

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