Submission #794941

#	Time	Username	Problem	Language	Result	Execution time	Memory
794941		Amylopectin	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	305 ms	29548 KiB

Main

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
const long long mxn = 1e6 + 10;
long long hei[mxn] = {},dif[mxn] = {},sta[mxn][2] = {},se[mxn][2][2] = {};
long long ab(long long l)
{
    if(l < 0)
    {
        return -l;
    }
    return l;
}
long long bui(long long cl,long long cr,long long no)
{
    if(cl == cr)
    {
        se[no][0][0] = 0;
        se[no][0][1] = 0;
        se[no][1][0] = 0;
        se[no][1][1] = ab(dif[cl]);
        // sta[no][0] = 1;
        // sta[no][1] = 1;
        return 0;
    }
    long long i,j,mid = (cl+cr) / 2;
    bui(cl,mid,no*2);
    bui(mid+1,cr,no*2+1);
    if(dif[mid] * dif[mid+1] >= 0)
    {
        for(i=0; i<2; i++)
        {
            for(j=0; j<2; j++)
            {
                se[no][i][j] = se[no*2][i][1] + se[no*2+1][1][j];
                if(j > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][i][0]);
                }
                if(i > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][0][j]);
                }
            }
        }
    }
    else 
    {
        for(i=0; i<2; i++)
        {
            for(j=0; j<2; j++)
            {
                se[no][i][j] = max(se[no*2][i][0] + se[no*2+1][1][j]
                ,se[no*2][i][1] + se[no*2+1][0][j]);
                if(j > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][i][0]);
                }
                if(i > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][0][j]);
                }
            }
        }
    }
    return 0;
}
long long ad(long long cl,long long cr,long long no,long long tar)
{
    if(cl > tar || cr < tar)
    {
        return 0;
    }
    if(cl == cr)
    {
        se[no][0][0] = 0;
        se[no][0][1] = 0;
        se[no][1][0] = 0;
        se[no][1][1] = ab(dif[cl]);
        // sta[no][0] = 1;
        // sta[no][1] = 1;
        return 0;
    }
    long long i,j,mid = (cl+cr) / 2;
    ad(cl,mid,no*2,tar);
    ad(mid+1,cr,no*2+1,tar);
    if(dif[mid] * dif[mid+1] >= 0)
    {
        for(i=0; i<2; i++)
        {
            for(j=0; j<2; j++)
            {
                se[no][i][j] = se[no*2][i][1] + se[no*2+1][1][j];
                if(j > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][i][0]);
                }
                if(i > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][0][j]);
                }
            }  
        }
    }
    else 
    {
        for(i=0; i<2; i++)
        {
            for(j=0; j<2; j++)
            {
                se[no][i][j] = max(se[no*2][i][0] + se[no*2+1][1][j]
                ,se[no*2][i][1] + se[no*2+1][0][j]);
                if(j > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][i][0]);
                }
                if(i > 0)
                {
                    se[no][i][j] = max(se[no][i][j],se[no][0][j]);
                }
            }
        }
    }
    return 0;
}
int main()
{
    long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
    scanf("%lld %lld",&n,&q);
    for(i=0; i<n; i++)
    {
        scanf("%lld",&hei[i]);
        if(i > 0)
        {
            dif[i-1] = hei[i] - hei[i-1];
        }
    }
    bui(0,n-2,1);
    for(i=0; i<q; i++)
    {
        scanf("%lld %lld %lld",&cl,&cr,&cva);
        cl --;
        cr --;
        if(cl > 0)
        {
            dif[cl-1] += cva;
            ad(0,n-2,1,cl-1);
        }
        if(cr < n-1)
        {
            dif[cr] -= cva;
            ad(0,n-2,1,cr);
        }
        printf("%lld\n",se[1][1][1]);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:17: warning: unused variable 'j' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                 ^
Main.cpp:129:21: warning: unused variable 'm' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                     ^
Main.cpp:129:25: warning: unused variable 'k' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                         ^
Main.cpp:129:27: warning: unused variable 'cn' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                           ^~
Main.cpp:129:30: warning: unused variable 'cm' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                              ^~
Main.cpp:129:33: warning: unused variable 'fn' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                                 ^~
Main.cpp:129:36: warning: unused variable 'fm' [-Wunused-variable]
  129 |     long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva;
      |                                    ^~
Main.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%lld %lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         scanf("%lld",&hei[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%lld %lld %lld",&cl,&cr,&cva);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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