oj.uz

Submission #242819

# Submission time Handle Problem Language Result Execution time Memory
242819 2020-06-29T10:51:04 Z moonrabbit2 Feast (NOI19_feast) C++17
47 / 100
 349 ms 228220 KB 
#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;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 228120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 228088 KB Output is correct
2 Correct 170 ms 228116 KB Output is correct
3 Correct 162 ms 228144 KB Output is correct
4 Correct 323 ms 228204 KB Output is correct
5 Correct 169 ms 228196 KB Output is correct
6 Correct 152 ms 228088 KB Output is correct
7 Correct 349 ms 228192 KB Output is correct
8 Correct 264 ms 228088 KB Output is correct
9 Correct 175 ms 228088 KB Output is correct
10 Correct 203 ms 228216 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 228088 KB Output is correct
2 Correct 180 ms 228172 KB Output is correct
3 Correct 181 ms 228088 KB Output is correct
4 Correct 182 ms 228088 KB Output is correct
5 Correct 183 ms 228088 KB Output is correct
6 Correct 183 ms 228220 KB Output is correct
7 Correct 186 ms 228088 KB Output is correct
8 Correct 199 ms 228088 KB Output is correct
9 Correct 180 ms 228220 KB Output is correct
10 Correct 180 ms 228088 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 225784 KB Output is correct
2 Correct 120 ms 225784 KB Output is correct
3 Correct 120 ms 225784 KB Output is correct
4 Correct 123 ms 225784 KB Output is correct
5 Correct 113 ms 225784 KB Output is correct
6 Correct 113 ms 225784 KB Output is correct
7 Correct 114 ms 225784 KB Output is correct
8 Correct 113 ms 225792 KB Output is correct
9 Correct 112 ms 225784 KB Output is correct
10 Correct 121 ms 225760 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 225784 KB Output is correct
2 Correct 120 ms 225784 KB Output is correct
3 Correct 120 ms 225784 KB Output is correct
4 Correct 123 ms 225784 KB Output is correct
5 Correct 113 ms 225784 KB Output is correct
6 Correct 113 ms 225784 KB Output is correct
7 Correct 114 ms 225784 KB Output is correct
8 Correct 113 ms 225792 KB Output is correct
9 Correct 112 ms 225784 KB Output is correct
10 Correct 121 ms 225760 KB Output is correct
11 Correct 115 ms 225836 KB Output is correct
12 Correct 114 ms 225784 KB Output is correct
13 Correct 112 ms 225784 KB Output is correct
14 Correct 115 ms 225784 KB Output is correct
15 Correct 112 ms 225784 KB Output is correct
16 Correct 121 ms 225784 KB Output is correct
17 Correct 114 ms 225912 KB Output is correct
18 Correct 119 ms 225788 KB Output is correct
19 Correct 114 ms 225784 KB Output is correct
20 Correct 113 ms 225760 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 225784 KB Output is correct
2 Correct 120 ms 225784 KB Output is correct
3 Correct 120 ms 225784 KB Output is correct
4 Correct 123 ms 225784 KB Output is correct
5 Correct 113 ms 225784 KB Output is correct
6 Correct 113 ms 225784 KB Output is correct
7 Correct 114 ms 225784 KB Output is correct
8 Correct 113 ms 225792 KB Output is correct
9 Correct 112 ms 225784 KB Output is correct
10 Correct 121 ms 225760 KB Output is correct
11 Correct 115 ms 225836 KB Output is correct
12 Correct 114 ms 225784 KB Output is correct
13 Correct 112 ms 225784 KB Output is correct
14 Correct 115 ms 225784 KB Output is correct
15 Correct 112 ms 225784 KB Output is correct
16 Correct 121 ms 225784 KB Output is correct
17 Correct 114 ms 225912 KB Output is correct
18 Correct 119 ms 225788 KB Output is correct
19 Correct 114 ms 225784 KB Output is correct
20 Correct 113 ms 225760 KB Output is correct
21 Correct 122 ms 225784 KB Output is correct
22 Incorrect 122 ms 225784 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 228120 KB Output isn't correct
2 Halted 0 ms 0 KB -