Submission #1042757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042757		modwwe	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	345 ms	42068 KiB

Main

//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=-1e14;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
int  i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
  //  fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    //  modwwe
    phongbeo();
}
int a[200001];
struct CI{
 int a,b;
    int f[2][2];
};
 int fe(CI a)
     {
          return max({a.f[0][0],a.f[0][1],a.f[1][0],a.f[1][1]});
     }
struct IT{
CI t[800001];
int t2[800001];
 CI mer(CI a,CI b)
 {
      CI c;
      for(int j=0;j<=1;j++)
        for(int z=0;z<=1;z++)
        c.f[j][z]=inf;
      for(int j=0;j<=1;j++)
        for(int z=0;z<=1;z++)
        if(a.f[j][z]!=inf)
        for(int j2=0;j2<=1;j2++)
        for(int z2=0;z2<=1;z2++)
        if(b.f[j2][z2]!=inf)
      {
          c.f[j][z2]=max(c.f[j][z2],a.f[j][z]+b.f[j2][z2]);
            if(a.b<b.a&&z!=j2&&z==1)
                c.f[j][z2]=max(c.f[j][z2],a.f[j][z]+b.f[j2][z2]+b.a-a.b);
            if(a.b>b.a&&z!=j2&&z==0)
                 c.f[j][z2]=max(c.f[j][z2],a.f[j][z]+b.f[j2][z2]+a.b-b.a);
      }
       c.a=a.a;
        c.b=b.b;
        return c;
 }
 void build(int node,int l,int r)
  {

       if(l==r)
       {
           for(int j=0;j<=1;j++)
        for(int z=0;z<=1;z++)
       t[node].f[j][z]=inf;
            for(int j=0;j<=1;j++)
            t[node].f[j][1-j]=0;
          t[node].a=a[l];
          t[node].b=a[l];
            return;
       }
       int mid=l+r>>1;
       build(node<<1,l,mid);
       build(node<<1|1,mid+1,r);
        t[node]=mer(t[node<<1],t[node<<1|1]);
       // cout<<fe(t[node])<<" "<<l<<" "<<r<<" "<<t[node].f[0][0],down
  }
  void ff(int x)
  {
       for(int i=x*2;i<=x*2+1;i++)
        t2[i]+=t2[x],
        t[i].a+=t2[x],
        t[i].b+=t2[x];
       t2[x]=0;
  }
  void upd(int node,int l,int r,int l1,int r1,int x)
   {
     if(l>r1||r<l1) return;
      if(l>=l1&&r<=r1)
      {
           t[node].a+=x;
           t[node].b+=x;
            t2[node]+=x;
            return;
      }
    if(t2[node]!=0)  ff(node);
     int mid=l+r>>1;
       upd(node<<1,l,mid,l1,r1,x);
       upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=mer(t[node<<1],t[node<<1|1]);
   }

}st;

void phongbeo()
{
    cin>>n>>m;

     for(int i=1;i<=n;i++)
         cin>>a[i];
      st.build(1,1,n);
     for(int i=1;i<=m;i++)
     {cin>>l>>r>>k;
          st.upd(1,1,n,l,r,k);
          cout<<fe(st.t[1]),down
     }
 }

Compilation message (stderr)

Main.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~
Main.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
Main.cpp:110:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |        int mid=l+r>>1;
      |                ~^~
Main.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:135:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |      int mid=l+r>>1;
      |              ~^~

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