#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
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);
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
4 ms |
852 KB |
Output is correct |
| 8 |
Correct |
4 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
852 KB |
Output is correct |
| 11 |
Correct |
4 ms |
852 KB |
Output is correct |
| 12 |
Correct |
4 ms |
848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
4 ms |
852 KB |
Output is correct |
| 8 |
Correct |
4 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
852 KB |
Output is correct |
| 11 |
Correct |
4 ms |
852 KB |
Output is correct |
| 12 |
Correct |
4 ms |
848 KB |
Output is correct |
| 13 |
Correct |
491 ms |
35644 KB |
Output is correct |
| 14 |
Correct |
441 ms |
35724 KB |
Output is correct |
| 15 |
Correct |
432 ms |
35648 KB |
Output is correct |
| 16 |
Correct |
461 ms |
35568 KB |
Output is correct |
| 17 |
Correct |
459 ms |
35468 KB |
Output is correct |
| 18 |
Correct |
430 ms |
36160 KB |
Output is correct |
