oj.uz

Submission #1083865

# Submission time Handle Problem Language Result Execution time Memory
1083865 2024-09-04T11:16:49 Z lamlamlam Feast (NOI19_feast) C++17
4 / 100
 60 ms 104784 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 = -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:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 101712 KB Output is correct
2 Correct 54 ms 104624 KB Output is correct
3 Correct 54 ms 104556 KB Output is correct
4 Correct 54 ms 104532 KB Output is correct
5 Correct 53 ms 104528 KB Output is correct
6 Correct 53 ms 104476 KB Output is correct
7 Correct 50 ms 104784 KB Output is correct
8 Correct 53 ms 104532 KB Output is correct
9 Correct 58 ms 104520 KB Output is correct
10 Correct 54 ms 104532 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 101716 KB Output is correct
2 Correct 41 ms 101712 KB Output is correct
3 Incorrect 43 ms 101804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 101712 KB Output is correct
2 Correct 54 ms 104624 KB Output is correct
3 Correct 54 ms 104556 KB Output is correct
4 Correct 54 ms 104532 KB Output is correct
5 Correct 53 ms 104528 KB Output is correct
6 Correct 53 ms 104476 KB Output is correct
7 Correct 50 ms 104784 KB Output is correct
8 Correct 53 ms 104532 KB Output is correct
9 Correct 58 ms 104520 KB Output is correct
10 Correct 54 ms 104532 KB Output is correct
11 Correct 45 ms 101716 KB Output is correct
12 Correct 41 ms 101712 KB Output is correct
13 Incorrect 43 ms 101804 KB Output isn't correct
14 Halted 0 ms 0 KB -