Submission #1261919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261919		sitingfake	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	514 ms	42412 KiB

Main

#include<bits/stdc++.h>
using namespace std;
// define
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ld long double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define flip(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define INF 0x3f
#define sitingfake 1
#define orz 1
#define task ""
//constant
const ll mod=1e9+7;
const long long linf=4557430888798830399;
const int inf=1061109567;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
// template function
template<typename T> bool maximize(T &a, const T &b)
{
    if(a<b)
    {
        a=b;
        return 1;
    }
    return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
    if(a>b)
    {
        a=b;
        return 1;
    }
    return 0;
}
const int maxn=2e5+8;
ll a[maxn];
int n,q;
struct SegTree
{
    struct Node
    {
        ll dp[2][2];
        ll L,R;
        Node ()
        {
            ms(dp,0);
        }
        Node operator + (Node &other)
        {
            Node ans;
            ans.L=L;
            ans.R=other.R;
            for(int l=0;l<2;l++)
            {
                for(int j=0;j<2;j++)
                {
                    for(int r=0;r<2;r++)
                    {
                        for(int k=0;k<2;k++)
                        {
                            if(j==1&&k==1&&((R<0)!=(other.L<0))) continue;
                            maximize(ans.dp[l][r],dp[l][j]+other.dp[k][r]);
                        }
                    }
                }
            }
            return ans;
        }
    };
    vector<Node>st;
    SegTree(int sz)
    {
        st.resize(4*sz+2);
    }
    void build(int i,int l,int r)
    {
        if(l==r)
        {
            st[i].L=st[i].R=a[l+1]-a[l];
            st[i].dp[1][1]=abs(st[i].L);
            return;
        }
        int m=(r+l)>>1;
        build(i*2,l,m);
        build(i*2+1,m+1,r);
        st[i]=st[i*2]+st[i*2+1];
    }
    void up(int i,int l,int r,int pos,ll val)
    {
        if(pos>r||pos<l) return;
        if(l==r)
        {
            st[i].L+=val;
            st[i].R+=val;
            st[i].dp[1][1]=abs(st[i].L);
            return;
        }
        int m=(r+l)>>1;
        up(i*2,l,m,pos,val);
        up(i*2+1,m+1,r,pos,val);
        st[i]=st[i*2]+st[i*2+1];
    }

};

signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }
   cin>>n>>q;
   for(int i=1;i<=n;i++) cin >> a[i];
   SegTree st(n);
   st.build(1,1,n-1);
   while (q--)
   {
       int l,r,x;
       cin >> l >> r >>x;
       if(l-1>=1) st.up(1,1,n-1,l-1,x);
       if(r<=n-1) st.up(1,1,n-1,r,-x);
       cout<<max({st.st[1].dp[0][0],st.st[1].dp[1][0],
                 st.st[1].dp[1][1],st.st[1].dp[0][1]})<<"\n";
   }
   //execute;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:124:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55