Submission #1236062

#TimeUsernameProblemLanguageResultExecution timeMemory
1236062SSSMMeasures (CEOI22_measures)C++20
100 / 100
136 ms23256 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("sse4") using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #define F first #define S second #define pb push_back #define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) //#define md(a) (a%mod+mod)%mod #define all(a) a.begin(), a.end() #define MP make_pair #define lc (id<<1) #define rc (lc|1) #define mid (l+r)/2 #define kill(a) cout << a << "\n", exit(0) #define SZ(a) (ll)a.size() typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll; typedef long double ld; typedef vector<vector<ll>> matrix; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn=5e5+10, mod=1e9+7, INF=1e9, LOG=20, sq=65; ll poww(ll a, ll b, ll mod) { if (b == 0) return 1; return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod; } ll n, m, d, A[maxn]; vector<ll> vec; struct Node{ ll cnt=0, ans=0, pref=0, suf=0; } seg[maxn<<2]; void Upd(ll x, ll l=0, ll r=SZ(vec), ll id=1) { //cout<<x<<" "<<l<<" "<<r<<" "<<id<<"\n"; if(l==r-1){ seg[id].cnt++; seg[id].ans=(seg[id].cnt-1)*d; seg[id].pref=seg[id].cnt*d; seg[id].suf=seg[id].cnt*d; return; } if(x<mid) Upd(x, l, mid, lc); else Upd(x, mid, r, rc); seg[id].cnt=seg[lc].cnt+seg[rc].cnt; seg[id].ans=max({seg[lc].ans, seg[rc].ans, seg[lc].suf+seg[rc].pref-(vec[mid]-vec[mid-1])-d}); seg[id].pref=max(seg[lc].pref, seg[rc].pref-(vec[mid]-vec[l])+seg[lc].cnt*d); seg[id].suf=max(seg[rc].suf, seg[lc].suf-(vec[r-1]-vec[mid-1])+seg[rc].cnt*d); } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>m>>d; for(ll i=1;i<=n+m;i++){ cin>>A[i]; vec.pb(A[i]); } sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); for(ll i=1;i<=n+m;i++){ ll x=lower_bound(all(vec), A[i])-vec.begin(); Upd(x); if(i>n){ cout<<seg[1].ans/2; if(seg[1].ans&1) cout<<".5"; cout<<" "; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...