oj.uz

Submission #376323

# Submission time Handle Problem Language Result Execution time Memory
376323 2021-03-11T08:32:21 Z tqbfjotld Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1064 ms 61676 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 9 ms 1132 KB Output is correct
8 Correct 7 ms 1260 KB Output is correct
9 Correct 7 ms 1260 KB Output is correct
10 Correct 7 ms 1260 KB Output is correct
11 Correct 7 ms 1260 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 9 ms 1132 KB Output is correct
8 Correct 7 ms 1260 KB Output is correct
9 Correct 7 ms 1260 KB Output is correct
10 Correct 7 ms 1260 KB Output is correct
11 Correct 7 ms 1260 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct
13 Correct 1049 ms 61164 KB Output is correct
14 Correct 1064 ms 61292 KB Output is correct
15 Correct 1054 ms 61276 KB Output is correct
16 Correct 1053 ms 61160 KB Output is correct
17 Correct 1014 ms 60956 KB Output is correct
18 Correct 998 ms 61676 KB Output is correct