제출 #900542

#제출 시각아이디문제언어결과실행 시간메모리
900542Shayan86Measures (CEOI22_measures)C++14
100 / 100
714 ms44736 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...