이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |