| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1083869 |
2024-09-04T11:20:20 Z |
lamlamlam |
Feast (NOI19_feast) |
C++17 |
|
76 ms |
134224 KB |
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
struct node
{
long long pre_max,pre_min,suf_max,suf_min,best,worst,sum;
int l_best,r_best,l_worst,r_worst,r_pre_max,r_pre_min,l_suf_max,l_suf_min,lazy;
node operator + (const node &o) const
{
node res;
res.sum = sum + o.sum;
res.pre_max = max(pre_max,sum+o.pre_max);
if(res.pre_max == pre_max) res.r_pre_max = r_pre_max;
else res.r_pre_max = o.r_pre_max;
res.pre_min = min(pre_min,sum+o.pre_min);
if(res.pre_min == pre_min) res.r_pre_min = r_pre_min;
else res.r_pre_min = o.r_pre_min;
res.suf_max = max(o.sum+suf_max,o.suf_max);
if(res.suf_max == o.sum+suf_max) res.l_suf_max = l_suf_max;
else res.l_suf_max = o.l_suf_max;
res.suf_min = min(o.sum+suf_min,o.suf_min);
if(res.suf_min == o.sum+suf_min) res.l_suf_min = l_suf_min;
else res.l_suf_min = o.l_suf_min;
res.best = max({best,o.best,suf_max+o.pre_max});
if(res.best == best){
res.l_best = l_best;
res.r_best = r_best;
}
else if(res.best == o.best){
res.l_best = o.l_best;
res.r_best = o.r_best;
}
else{
res.l_best = l_suf_max;
res.r_best = o.r_pre_max;
}
res.worst = min({worst,o.worst,suf_min+o.pre_min});
if(res.worst == worst){
res.l_worst = l_worst;
res.r_worst = r_worst;
}
else if(res.worst == o.worst){
res.l_worst = o.l_worst;
res.r_worst = o.r_worst;
}
else{
res.l_worst = l_suf_min;
res.r_worst = o.r_pre_min;
}
return res;
}
};
node rev(node x)
{
x.pre_max = -x.pre_max;
x.pre_min = -x.pre_min;
x.suf_max = -x.suf_max;
x.suf_min = -x.suf_min;
x.best = -x.best;
x.worst = -x.worst;
x.sum = -x.sum;
swap(x.pre_max,x.pre_min);
swap(x.suf_max,x.suf_min);
swap(x.best,x.worst);
swap(x.l_best,x.l_worst);
swap(x.r_best,x.r_worst);
swap(x.r_pre_max,x.r_pre_min);
swap(x.l_suf_max,x.l_suf_min);
return x;
}
const int MN = 3e5+5;
const long long inf = 1e18;
int n,k,a[MN];
long long ans;
node st[MN*4];
void fix(int v,int l,int r)
{
if(st[v].lazy%2==0) return;
st[v] = rev(st[v]);
st[v].lazy = 0;
if(l==r) return;
st[v*2].lazy++;
st[v*2+1].lazy++;
}
void build(int v,int l,int r)
{
if(l==r){
st[v].pre_max = st[v].pre_min = st[v].suf_max = st[v].suf_min = st[v].best = st[v].worst = st[v].sum = a[l];
st[v].l_best = st[v].r_best = st[v].l_worst = st[v].r_worst = st[v].r_pre_max = st[v].r_pre_min = st[v].l_suf_max = st[v].l_suf_min = l;
return;
}
int mid = (l+r) >> 1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
st[v] = st[v*2] + st[v*2+1];
}
void upd(int v,int l,int r,int x,int y)
{
fix(v,l,r);
if(x>r or y<l) return;
if(x<=l and r<=y){
ans += st[v].sum;
st[v].lazy++;
fix(v,l,r);
return;
}
int mid = (l+r) >> 1;
upd(v*2,l,mid,x,y);
upd(v*2+1,mid+1,r,x,y);
st[v] = st[v*2] + st[v*2+1];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task "NOI19_feast"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
build(1,1,n);
while(k--){
fix(1,1,n);
int l = st[1].l_best;
int r = st[1].r_best;
//cout << l << ' ' << r << ' ' << st[1].best << ' ' << st[1].worst << endl;
if(st[1].best<=0) break;
upd(1,1,n,l,r);
}
cout << ans;
cerr << "\nTime: " << clock();
}
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
134224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
134180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
134224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
134224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
