Submission #242823

#	Time	Username	Problem	Language	Result	Execution time	Memory
242823		moonrabbit2	Feast (NOI19_feast)	C++17	100 / 100	417 ms	232220 KiB

feast

#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++){
		if(get<0>(Solver.tree[1].Mx)<=0) break;
		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;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29