Submission #242819

#TimeUsernameProblemLanguageResultExecution timeMemory
242819moonrabbit2Feast (NOI19_feast)C++17
47 / 100
349 ms228220 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef long double db; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<db,db> pdb; typedef tuple<int,int,int> tii; typedef tuple<ll,ll,ll> tll; typedef tuple<int,int,int,int> ti4; typedef vector<vector<ll>> mat; const ll mod=1e9+7,inf=1e18; const int N=3e5+5,M=2e5+5,K=1e7+5; int n,k; ll a[N],ans; struct SEG{ struct node{ tll Lmx,Rmx,Sum,Mx; tll Lmx2,Rmx2,Sum2,Mx2; void Swap(){ swap(Lmx,Lmx2); swap(Rmx,Rmx2); swap(Sum,Sum2); swap(Mx,Mx2); } node operator +(node n1){ node n; n.Lmx=max(Lmx,{get<0>(Sum)+get<0>(n1.Lmx),get<1>(Sum),get<2>(n1.Lmx)}); n.Rmx=max(n1.Rmx,{get<0>(Rmx)+get<0>(n1.Sum),get<1>(Rmx),get<2>(n1.Sum)}); n.Sum={get<0>(Sum)+get<0>(n1.Sum),get<1>(Sum),get<2>(n1.Sum)}; n.Mx=max({Mx,n1.Mx,{get<0>(Rmx)+get<0>(n1.Lmx),get<1>(Rmx),get<2>(n1.Lmx)}}); n.Lmx2=max(Lmx2,{get<0>(Sum2)+get<0>(n1.Lmx2),get<1>(Sum2),get<2>(n1.Lmx2)}); n.Rmx2=max(n1.Rmx2,{get<0>(Rmx2)+get<0>(n1.Sum2),get<1>(Rmx2),get<2>(n1.Sum2)}); n.Sum2={get<0>(Sum2)+get<0>(n1.Sum2),get<1>(Sum2),get<2>(n1.Sum2)}; n.Mx2=max({Mx2,n1.Mx2,{get<0>(Rmx2)+get<0>(n1.Lmx2),get<1>(Rmx2),get<2>(n1.Lmx2)}}); return n; } }tree[4*N]; bool lazy[4*N]; void pd(int nd,int l,int r){ if(lazy[nd]) tree[nd].Swap(); if(l!=r){ lazy[nd<<1]^=lazy[nd]; lazy[nd<<1|1]^=lazy[nd]; } lazy[nd]=0; } void init(int nd,int l,int r){ if(l==r){ tll t1={a[l],l,l},t2={-a[l],l,l}; tree[nd]={t1,t1,t1,t1,t2,t2,t2,t2}; return; } int m=(l+r)>>1; init(nd<<1,l,m); init(nd<<1|1,m+1,r); tree[nd]=tree[nd<<1]+tree[nd<<1|1]; } void upd(int nd,int l,int r,int s,int e){ pd(nd,l,r); if(r<s||e<l) return; if(s<=l&&r<=e){ lazy[nd]=1; pd(nd,l,r); return; } int m=(l+r)>>1; upd(nd<<1,l,m,s,e); upd(nd<<1|1,m+1,r,s,e); tree[nd]=tree[nd<<1]+tree[nd<<1|1]; } }Solver; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; Solver.init(1,1,n); for(int i=1;i<=k;i++){ ans+=get<0>(Solver.tree[1].Mx); Solver.upd(1,1,n,get<1>(Solver.tree[1].Mx),get<2>(Solver.tree[1].Mx)); } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...