oj.uz

Submission #1083862

# Submission time Handle Problem Language Result Execution time Memory
1083862 2024-09-04T11:07:47 Z lamlamlam Feast (NOI19_feast) C++17
0 / 100
 72 ms 104752 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
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 *= -1;
    x.pre_min *= -1;
    x.suf_max *= -1;
    x.suf_min *= -1;
    x.best *= -1;
    x.worst *= -1;
    x.sum *= -1;
    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],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;
        //if(x==2 and y==3) cout << endl << l << ' ' << r << ' ' << v << ' ' << st[v].best << ' ' << st[v].worst << endl;
        st[v].lazy++;
        fix(v,l,r);
        //if(x==2 and y==3) cout << l << ' ' << r << ' ' << v << ' ' << st[v].best << ' ' << st[v].worst << endl << endl;
        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];
    //if(x==2 and y==3) cout << l << ' ' << r << ' ' << v << ' ' << st[v].best << ' ' << st[v].worst << endl;
}

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: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".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 102752 KB Output is correct
2 Correct 46 ms 102788 KB Output is correct
3 Incorrect 46 ms 102740 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

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