oj.uz

Submission #735500

# Submission time Handle Problem Language Result Execution time Memory
735500 2023-05-04T08:26:27 Z bgnbvnbv Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 700 ms 69548 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct node
{
    ll dau,cuoi;
    ll a[2][2];
    node()
    {
        dau=0,cuoi=0;
        for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=0;
    }
    node operator+(const node&o)
    {
        node ans;
        ans.dau=dau;
        ans.cuoi=o.cuoi;
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    ans.a[i][j]=max(ans.a[i][j],a[i][k]+o.a[1-k][j]);
                }
                if(cuoi*o.dau>0) ans.a[i][j]=max(ans.a[i][j],a[i][1]+o.a[1][j]);
            }
        }
        return ans;
    }
}st[4*maxN];
void update(ll pos,ll val,ll id=1,ll l=2,ll r=n)
{
    if(pos==1) return;
    if(l==r)
    {
        st[id].dau=st[id].cuoi=val;
        st[id].a[1][1]=abs(val);
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
ll q,a[maxN],b[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i],update(i,a[i]-a[i-1]),b[i]=a[i]-a[i-1];
    for(int i=1;i<=q;i++)
    {
        ll l,r,x;
        cin >> l >> r >> x;
        b[l]+=x;
        update(l,b[l]);
        r++;
        if(r<=n)
        {
            b[r]-=x;
            update(r,b[r]);
        }
        cout<< max({st[1].a[0][0],st[1].a[1][0],st[1].a[1][1],st[1].a[0][1]})<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

Main.cpp: In function 'void update(ll, ll, ll, ll, ll)':
Main.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 28 ms 56652 KB Output is correct
3 Correct 27 ms 56660 KB Output is correct
4 Correct 28 ms 56640 KB Output is correct
5 Correct 29 ms 56660 KB Output is correct
6 Correct 33 ms 56668 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 28 ms 56652 KB Output is correct
3 Correct 27 ms 56660 KB Output is correct
4 Correct 28 ms 56640 KB Output is correct
5 Correct 29 ms 56660 KB Output is correct
6 Correct 33 ms 56668 KB Output is correct
7 Correct 31 ms 56844 KB Output is correct
8 Correct 30 ms 56848 KB Output is correct
9 Correct 32 ms 56788 KB Output is correct
10 Correct 31 ms 56820 KB Output is correct
11 Correct 34 ms 56776 KB Output is correct
12 Correct 35 ms 56852 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 28 ms 56652 KB Output is correct
3 Correct 27 ms 56660 KB Output is correct
4 Correct 28 ms 56640 KB Output is correct
5 Correct 29 ms 56660 KB Output is correct
6 Correct 33 ms 56668 KB Output is correct
7 Correct 31 ms 56844 KB Output is correct
8 Correct 30 ms 56848 KB Output is correct
9 Correct 32 ms 56788 KB Output is correct
10 Correct 31 ms 56820 KB Output is correct
11 Correct 34 ms 56776 KB Output is correct
12 Correct 35 ms 56852 KB Output is correct
13 Correct 700 ms 68864 KB Output is correct
14 Correct 697 ms 68896 KB Output is correct
15 Correct 673 ms 68904 KB Output is correct
16 Correct 632 ms 68912 KB Output is correct
17 Correct 649 ms 68764 KB Output is correct
18 Correct 565 ms 69548 KB Output is correct