Submission #674240

#	Time	Username	Problem	Language	Result	Execution time	Memory
674240		Samrev	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	491 ms	36160 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lli;
typedef long double lld;
typedef priority_queue <lli , vector<lli>, greater<lli> > min_heap;
typedef priority_queue <lli> max_heap;
typedef pair<lli, lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
const lli  M = 1e9 + 7;
const lli M1 = 0;
const lli M2 = 1000000000000000001;
lli mod(lli x){   return (x%M);}
lli mod_minus(lli a, lli b){ lli ans= (mod(a)-mod(b)); if(ans<0) ans=mod(ans+M); return ans;}
lli mod_mul(lli a,lli b){  return mod(mod(a)*mod(b));}
lli mod_add(lli a,lli b){ return mod(mod(a)+mod(b));}
#define FOR(i,l,u) for(int i=l;i<=u;i++)
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
#define All(A) A.begin(),A.end()
#define isPowerOfTwo(x) (x && (!(x&(x-1))))
#define LSOne(S) (S & (-S))
#define set_count(i)  __builtin_popcount(i)
lli gcd(lli a, lli b) { return b == 0 ? a : gcd(b, a % b); }
lli lcm(lli a, lli b) { return a * (b / gcd(a, b)); }
lli phi(lli n) {
    lli result = n;
    for (lli i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
 
lli ceill(lli a,lli b)
{
    if(a%b==0)
        return a/b;
    else
        return a/b +1;
}
 
lli extendted_gcd(lli a ,lli b,lli &x,lli &y){
    if(a==0){
        x=0;y=1;return b;}
        lli x1,y1,ans = extendted_gcd(b%a,a,x1,y1);
        x = y1-(b/a)*x1;y = x1;
        return ans;
    }
lli power_mod(lli a,lli b,lli m)
{
    lli ans =1;
    while(b!=0)
    {
        if(b%2==1)
            ans=(ans*a)%m;
        a=a*a;
        a%=m;
        b/=2;
    }
    return ans;
}
lli mod_inverse(lli a,lli m)
{
    return power_mod(a,m-2,m);
}
void mod_inverse_array(lli inv[],lli u,lli m)
{
    inv[1]=1;
    FOR(i,2,u){
        inv[i]=((-(m/i)*inv[m%i]%m)+m)%m;
    }
}
lli N_C_r_mod_m(lli N,lli r , vector<lli> factorial)
{
    lli a = factorial[N],b = mod_inverse(factorial[N-r],M),c = mod_inverse(factorial[r],M);
    return mod_mul(a,mod_mul(b,c));
}
void prime_factorization(lli n,unordered_map<lli,lli> &m)
{
    lli i=2;
    while(n%i==0)
    {
        m[i]++;
        n=n/i;
    }
    for(i=3;i*i<=n;i+=2)
    {
        while(n%i==0)
        {
            m[i]++;
            n=n/i;
        }
    }
    if(n!=1)   
        m[n]++;
}
 
void linear_sieve(vector<lli> &pr,vector<lli> &lp,lli N)
{
    for (lli i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
 
        for (lli j=0; j<(lli)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
 
    }
 
 
}
 
lli eval_poly(vector<lli> coeff , lli x){
    lli degree = coeff.size(); //coeff are as 0,1,2----n
    degree--;
    lli ans = 0;
    for(lli i = degree ; i>=0 ; i--){
        ans = (x*ans + coeff[i]);
    }
    return ans;
}
 
lli derivative_poly(vector<lli> coeff , lli x){
    lli degree = coeff.size(); //coeff are as 0,1,2----n
    degree--;
    lli ans = 0;
    lli pow = 1;
    for(lli i = 1; i<=degree;i++){
        ans+=(i*pow*coeff[i]);
        pow*=x;
    }
    return ans;
 
}
int t = 1;
int n , q;
struct item{
    lli NN,NY,YN,YY,L,R; 
};
vector<lli> D;
vector<item> values;
struct item ZERO = {0,0,0,0,0,0};
int sizer = 1; 
item single(lli i){
    return {
        NN : 0,
        NY : 0,
        YN : 0,
        YY : abs(i),
        L : i,
        R : i
    };
}
lli check(item a, item b){
    return (a.R*b.L)>0;
}
lli maxi(lli a, lli b, lli c, lli d){
    return max(a , max(b , max(c , d)));
}
item merge(item a , item b){
    return{
        NN : maxi(a.NN + b.NN , a.NN + b.YN , a.NY + b.NN , check(a,b)*(a.NY + b.YN) ),
        NY : maxi(a.NN + b.NY , a.NN + b.YY , a.NY + b.NY , check(a,b)*(a.NY + b.YY) ),
        YN : maxi(a.YN + b.NN , a.YN + b.YN , a.YY + b.NN , check(a,b)*(a.YY + b.YN) ),
        YY : maxi(a.YN + b.NY , a.YN + b.YY , a.YY + b.NY , check(a,b)*(a.YY + b.YY) ),
        L : a.L,
        R : b.R
    };
}
void build(vector<lli> &D , lli x=0,lli lx = 0 ,lli rx = sizer){
    if((rx - lx)<=1){
        if(lx<D.size()){
            values[x] = single(D[lx]);
        }
        return;
    }
    lli m = lx + (rx - lx)/2;
    build(D,2*x + 1, lx , m);
    build(D , 2*x + 2, m , rx);
    values[x] = merge(values[2*x + 1], values[2*x + 2]);
}
void update(lli i , lli v , lli x = 0 , lli lx = 0 , lli rx = sizer){
    if((rx - lx)<=1){
        values[x] = single(v + values[x].L);
        return;
    }
    lli m = lx + (rx - lx)/2;
    if(i<m) update(i,v,2*x + 1,lx , m);
    else update(i , v, 2*x + 2, m , rx);

    values[x] = merge(values[2*x +1], values[2*x + 2]);
}

void solve(){
   cin>>n>>q;
   while(sizer < (n-1)) sizer*=2;
   values.resize(2*sizer);
   lli a,b;
   D.resize(n-1);
   cin>>a;
   FOR(i,0,n-2){
        cin>>b;
        D[i] = b-a;
        swap(a,b);
   }

   build(D);

   FOR(i,1,q){
        lli l , r, v;
        cin>>l>>r>>v;
        l--,r--;
        if(l>0) update(l-1,v);
        if(r<D.size()) update(r,-v);
        cout<<values[0].YY<<"\n";
   }
}
    

int main()
{
 
    FAST;
    // g++ -o output prac.cpp
    // .\output
    // cin>>t;

    // freopen("optmilk.in","r",stdin);
	// freopen("optmilk.out","w",stdout);
    while(t--){
        solve();

    }
    return 0;
 
}

Compilation message (stderr)

Main.cpp: In function 'void build(std::vector<long long int>&, lli, lli, lli)':
Main.cpp:183:14: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         if(lx<D.size()){
      |            ~~^~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:225:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         if(r<D.size()) update(r,-v);
      |            ~^~~~~~~~~

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