Submission #376323

#	Time	Username	Problem	Language	Result	Execution time	Memory
376323		tqbfjotld	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1064 ms	61676 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct val{
    int v1,vn;
    int up1,upn;
    int ansLR, ansL, ansR, ans;
    val(){
    }
    val(int v){
        v1 = v; vn = v;
        up1 = -1; upn = -1;
        ansLR = ansL = ansR = ans = 0;
    }
};

val join(val a, val b){
    val ans = val();
    ans.v1 = a.v1;
    ans.vn = b.vn;
    if (a.up1==-1){
        if (b.up1==-1){
            ans.up1 = b.v1>a.v1;
            ans.upn = b.v1>a.v1;
            ans.ansLR = abs(b.v1-a.v1);
            ans.ansL = ans.ansR = ans.ans = 0;
            return ans;
        }
        ans.up1 = b.v1>a.v1;
        ans.upn = b.upn;
        if (b.up1 && b.v1>a.v1){
            ans.ansLR = b.ansLR+b.v1-a.v1;
            ans.ansL = b.ansL+b.v1-a.v1;
            ans.ansR = b.ansLR;
            ans.ans = b.ansL;
        }
        else if ((!b.up1)&&b.v1<a.v1){
            ans.ansLR = b.ansLR-b.v1+a.v1;
            ans.ansL = b.ansL-b.v1+a.v1;
            ans.ansR = b.ansLR;
            ans.ans = b.ansL;
        }
        else {
            ans.ansLR = max(b.ansR+abs(b.v1-a.v1),b.ansLR);
            ans.ansL = max(b.ans+abs(b.v1-a.v1),b.ansL);
            ans.ansR = b.ansLR;
            ans.ans = b.ansL;
        }
    }
    else if (b.up1==-1){
        ans.up1 = a.up1;
        ans.upn = b.v1>a.vn;
        if (a.upn!=(a.vn>b.v1)){
            ans.ansL = a.ansLR;
            ans.ans = a.ansR;
            ans.ansLR = a.ansLR+abs(a.vn-b.v1);
            ans.ansR = a.ansR + abs(a.vn-b.v1);
        }
        else{
            ans.ansLR = max(a.ansL + abs(a.vn-b.v1),a.ansLR);
            ans.ansR = max(a.ans+abs(a.vn-b.v1),a.ansR);
            ans.ansL = a.ansLR;
            ans.ans = a.ansR;
        }
    }
    else{
        ans.up1 = a.up1;
        ans.upn = b.upn;
        if (a.upn==b.up1){
            if ((a.vn<b.v1)==a.upn){
                ans.ansLR = a.ansLR+b.ansLR+abs(a.vn-b.v1);
                ans.ansL = a.ansLR + b.ansL + abs(a.vn-b.v1);
                ans.ansR = a.ansR + b.ansLR + abs(a.vn-b.v1);
                ans.ans = a.ansR + b.ansL + abs(a.vn-b.v1);
            }
            else{
                ans.ansLR = max(a.ansLR+b.ansLR,a.ansL+b.ansR+abs(a.vn-b.v1));
                ans.ansL = max(a.ansLR+b.ansL, a.ansL+b.ans+abs(a.vn-b.v1));
                ans.ansR = max(a.ansR+b.ansLR,a.ans+b.ansR+abs(a.vn-b.v1));
                ans.ans = max(a.ansR+b.ansL,a.ans+b.ans+abs(a.vn-b.v1));
            }
        }
        else{
            if ((a.vn<b.v1)==a.upn){
                ans.ansLR = max(a.ansLR+b.ansLR,a.ansLR+b.ansR+abs(a.vn-b.v1));
                ans.ansR = max(a.ansR+b.ansLR,a.ansR+b.ansR+abs(a.vn-b.v1));
                ans.ansL = max(a.ansLR+b.ansL,a.ansLR+b.ans+abs(a.vn-b.v1));
                ans.ans = max(a.ansR+b.ansL, a.ansR+b.ans+abs(a.vn-b.v1));
            }
            else{
                ans.ansLR = max(a.ansLR+b.ansLR,a.ansL+b.ansLR+abs(a.vn-b.v1));
                ans.ansR = max(a.ansR+b.ansLR,a.ans+b.ansLR+abs(a.vn-b.v1));
                ans.ansL = max(a.ansLR+b.ansL,a.ansL+b.ansL+abs(a.vn-b.v1));
                ans.ans = max(a.ansR+b.ansL,a.ans+b.ansL+abs(a.vn-b.v1));
            }
        }
    }
    return ans;
}

int arr[200005];

struct node{
    int s,e;
    val v;
    bool lazyflag = false;
    int lazyval;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        lazyval = 0;
        if (s==e){
            v = val(arr[s]);
        }
        else {
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            v = join(l->v,r->v);
        }
    }
    void proc(){
        if (lazyflag){
            lazyflag = false;
            v.v1 += lazyval;
            v.vn += lazyval;
            if (s!=e){
                l->lazyflag = true;
                r->lazyflag = true;
                l->lazyval+=lazyval;
                r->lazyval+=lazyval;
            }
            lazyval = 0;
        }
    }
    void upd(int a, int b, int amt){
        proc();
        if (a<=s && e<=b){
            lazyflag = true;
            lazyval += amt;
            proc();
            return;
        }
        if (b<=(s+e)/2){
            l->upd(a,b,amt);
        }
        else if (a>(s+e)/2){
            r->upd(a,b,amt);
        }
        else {
            l->upd(a,b,amt); r->upd(a,b,amt);
        }
        l->proc(); r->proc();
        v = join(l->v,r->v);
    }
}*root;

 main(){
    int n,q;
    scanf("%lld%lld",&n,&q);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr[x]);
    }
    root = new node(0,n-1);
    for (int x = 0; x<q; x++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        a--;b--;
        root->upd(a,b,c);
        printf("%lld\n",root->v.ansLR);
    }
}

Compilation message (stderr)

Main.cpp:158:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  158 |  main(){
      |       ^
Main.cpp: In function 'int main()':
Main.cpp:160:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |     scanf("%lld%lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |         scanf("%lld",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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