oj.uz

Submission #873863

# Submission time Handle Problem Language Result Execution time Memory
873863 2023-11-16T02:01:27 Z damwuan Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 289 ms 30292 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+10;
const ll N=1e5;
const ll offset=1e18;
const double eps= 1e-9;
//const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,q,a[maxn],d[maxn];
int st[maxn*4][2][2];

void Update(int u,int val,int id=1,int l=1,int r=n-1)
{
    if (l==r)
    {
        d[l]+=val;
        st[id][1][1]=abs(d[l]);
        st[id][1][0]=-inf;
        st[id][0][1]=-inf;
        st[id][0][0]=0;
        return;
    }
    int mid=l+r>>1;
    if (u<=mid) Update(u,val,id*2,l,mid);
    else Update(u,val,id*2+1,mid+1,r);
    st[id][0][0]=max({st[id*2][0][1]+st[id*2+1][0][0],st[id*2][0][0]+st[id*2+1][1][0],st[id*2][0][0]+st[id*2+1][0][0]});
    st[id][1][0]=max({st[id*2][1][1]+st[id*2+1][0][0],st[id*2][1][0]+st[id*2+1][1][0],st[id*2][1][0]+st[id*2+1][0][0]});
    st[id][0][1]=max({st[id*2][0][1]+st[id*2+1][0][1],st[id*2][0][0]+st[id*2+1][1][1],st[id*2][0][0]+st[id*2+1][0][1]});
    st[id][1][1]=max({st[id*2][1][1]+st[id*2+1][0][1],st[id*2][1][0]+st[id*2+1][1][1],st[id*2][1][0]+st[id*2+1][0][1]});
    if (d[mid]*d[mid+1]>=0)
    {
        st[id][0][0]=max(st[id][0][0],st[id*2][0][1]+st[id*2+1][1][0]);
        st[id][1][0]=max(st[id][1][0],st[id*2][1][1]+st[id*2+1][1][0]);
        st[id][0][1]=max(st[id][0][1],st[id*2][0][1]+st[id*2+1][1][1]);
        st[id][1][1]=max(st[id][1][1],st[id*2][1][1]+st[id*2+1][1][1]);
    }
}

void sol()
{
    cin >> n>> q;
    for1(i,1,n)
    {
        cin >> a[i];
    }
    for1(i,1,n-1)
    {
        Update(i,a[i+1]-a[i]);
    }
//    cerr<<max({st[1][0][0],st[1][1][0],st[1][0][1],st[1][1][1]});
    for1(i,1,q)
    {
        int l,r,x; cin >> l>>r>>x;
        if (l-1>=1) Update(l-1,x);
        if (r<n) Update(r,-x);
        cout <<max({st[1][0][0],st[1][1][0],st[1][0][1],st[1][1][1]})<<'\n';
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("SUBSET.inp","r",stdin);
//    freopen("SUBSET.out","w",stdout);
    int t=1;
    //cin >> t;
    while (t--)
    {
        sol();
    }
}
/*
1 3 4
1 1
1 3
3 1
3 3
*/
/*
0 1 1 3.3
0 0 1 12.5
1 0 1 12.5
1 2 0 9.4625
2 0 0 12.5
2 0 1 13.05
3 1 0 13.2431
5 0 0 14.4931
14.493055556
*/

Compilation message

Main.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2524 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2524 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 3 ms 4864 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2524 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 3 ms 4864 KB Output is correct
13 Correct 271 ms 29468 KB Output is correct
14 Correct 275 ms 29496 KB Output is correct
15 Correct 265 ms 29524 KB Output is correct
16 Correct 289 ms 29300 KB Output is correct
17 Correct 267 ms 29376 KB Output is correct
18 Correct 238 ms 30292 KB Output is correct