oj.uz

Submission #284273

# Submission time Handle Problem Language Result Execution time Memory
284273 2020-08-27T06:37:34 Z 문홍윤(#5761) Progression (NOI20_progression) C++17
55 / 100
 1230 ms 65144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL llinf=2e18;

struct SEGMENT_TREE{
    struct NODE{
        bool setz;
        LL lzy, l, r, sum;
        int nl, nr, ans;
    }tree[1200000];
    struct QUERY_NODE{
        LL l, r;
        int nl, nr, ans, len;
    };
    void prop(int point, int s, int e){
        if(tree[point].setz){
            if(s!=e){
                tree[point*2].setz=true;
                tree[point*2+1].setz=true;
                tree[point*2].lzy=tree[point].lzy;
                tree[point*2+1].lzy=tree[point].lzy;
            }
            else{
                tree[point].l=tree[point].lzy;
                tree[point].r=tree[point].lzy;
                tree[point].sum=tree[point].l;
            }
        }
        else{
            if(s!=e){
                tree[point*2].lzy+=tree[point].lzy;
                tree[point*2+1].lzy+=tree[point].lzy;
            }
            else{
                tree[point].l+=tree[point].lzy;
                tree[point].r+=tree[point].lzy;
                tree[point].sum=tree[point].l;
            }
        }
        tree[point].lzy=0;
        tree[point].setz=false;
    }
    void eat(int point, int s, int e){
        if(s==e)return;
        LL ll, lr, rl, rr, sl, sr;
        int nll, nlr, nrl, nrr, al, ar;
        int mid=(s+e)/2;
        if(tree[point*2].setz){
            ll=lr=tree[point*2].lzy;
            sl=tree[point*2].lzy*(mid-s+1);
            nll=nlr=al=mid-s+1;
        }
        else{
            ll=tree[point*2].l+tree[point*2].lzy;
            lr=tree[point*2].r+tree[point*2].lzy;
            sl=tree[point*2].sum+tree[point*2].lzy*(mid-s+1);
            nll=tree[point*2].nl;
            nlr=tree[point*2].nr;
            al=tree[point*2].ans;
        }
        if(tree[point*2+1].setz){
            rl=rr=tree[point*2+1].lzy;
            sr=tree[point*2+1].lzy*(e-mid);
            nrl=nrr=ar=e-mid;
        }
        else{
            rl=tree[point*2+1].l+tree[point*2+1].lzy;
            rr=tree[point*2+1].r+tree[point*2+1].lzy;
            sr=tree[point*2+1].sum+tree[point*2+1].lzy*(e-mid);
            nrl=tree[point*2+1].nl;
            nrr=tree[point*2+1].nr;
            ar=tree[point*2+1].ans;
        }
        tree[point].ans=max(al, ar);
        tree[point].nl=nll;
        tree[point].nr=nrr;
        tree[point].sum=sl+sr;
        tree[point].l=ll;
        tree[point].r=rr;
        if(lr==rl){
            tree[point].ans=max(tree[point].ans, nlr+nrl);
            if(nll==mid-s+1)tree[point].nl=nll+nrl;
            if(nrr==e-mid)tree[point].nr=nrr+nlr;
        }
    }
    void init(int point, int s, int e){
        tree[point].ans=tree[point].nl=tree[point].nr=e-s+1;
        if(s==e)return;
        init(point*2, s, (s+e)/2);
        init(point*2+1, (s+e)/2+1, e);
    }
    void upd(int point, int s, int e, int a, int b, LL val, bool str){
        if(e<a||s>b)return;
        prop(point, s, e);
        if(a<=s&&e<=b){
            if(str){
                tree[point].setz=true;
                tree[point].lzy=val;
            }
            else tree[point].lzy+=val;
            return;
        }
        upd(point*2, s, (s+e)/2, a, b, val, str);
        upd(point*2+1, (s+e)/2+1, e, a, b, val, str);
        eat(point, s, e);
    }
    QUERY_NODE calc(QUERY_NODE a, QUERY_NODE b){
        QUERY_NODE ret;
        ret.len=a.len+b.len;
        ret.ans=max(a.ans, b.ans);
        ret.l=a.l, ret.r=b.r;
        ret.nl=a.nl, ret.nr=b.nr;
        if(a.r==b.l){
            if(a.nl==a.len)ret.nl=a.nl+b.nl;
            if(b.nr==b.len)ret.nr=b.nr+a.nr;
            ret.ans=max(ret.ans, a.nr+b.nl);
        }
        return ret;
    }
    QUERY_NODE query2(int point, int s, int e, int a, int b){
        if(e<a||s>b)return {llinf, llinf, -1, -1, -1, 0};
        prop(point, s, e);
        if(a<=s&&e<=b){
            eat(point, s, e);
            return {tree[point].l, tree[point].r, tree[point].nl, tree[point].nr, tree[point].ans, e-s+1};
        }
        QUERY_NODE qa=query2(point*2, s, (s+e)/2, a, b);
        QUERY_NODE qb=query2(point*2+1, (s+e)/2+1, e, a, b);
        eat(point, s, e);
        if(qa.l==llinf)return qb;
        if(qb.l==llinf)return qa;
        return calc(qa, qb);
    }
    int query(int point, int s, int e, int a, int b){
        if(a>b)return 1;
        return query2(point, s, e, a, b).ans+1;
    }
    LL get_sum(int point, int s, int e, int a, int b){
        if(e<a||s>b)return 0;
        prop(point, s, e);
        if(a<=s&&e<=b){
            eat(point, s, e);
            return tree[point].sum;
        }
        LL ret=0;
        ret+=get_sum(point*2, s, (s+e)/2, a, b);
        ret+=get_sum(point*2+1, (s+e)/2+1, e, a, b);
        eat(point, s, e);
        return ret;
    }
}seg;

int n, q;
LL arr[300010];

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++)scanf("%lld", &arr[i]);
    seg.init(1, 1, n);
    for(int i=1; i<=n; i++)seg.upd(1, 1, n, i, i, arr[i]-arr[i-1], true);
    for(int i=1; i<=q; i++){
        int qt, a, b;
        scanf("%d", &qt);
        if(qt==1){
            LL c, d;
            scanf("%d %d %lld %lld", &a, &b, &c, &d);
            if(a+1<=b)seg.upd(1, 1, n, a+1, b, d, false);
            seg.upd(1, 1, n, a, a, c, false);
            if(b<n)seg.upd(1, 1, n, b+1, b+1, -c-d*(b-a), false);
        }
        if(qt==2){
            LL c, d, fr, re;
            scanf("%d %d %lld %lld", &a, &b, &c, &d);
            re=seg.get_sum(1, 1, n, 1, b+1);
            fr=seg.get_sum(1, 1, n, 1, a-1);
            if(a+1<=b)seg.upd(1, 1, n, a+1, b, d, true);
            seg.upd(1, 1, n, a, a, c-fr, true);
            if(b<n)seg.upd(1, 1, n, b+1, b+1, re-c-d*(b-a), true);
        }
        if(qt==3){
            scanf("%d %d", &a, &b);
            printf("%d\n", seg.query(1, 1, n, a+1, b));
        }
    }
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Progression.cpp:159:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |     for(int i=1; i<=n; i++)scanf("%lld", &arr[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~~
Progression.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |         scanf("%d", &qt);
      |         ~~~~~^~~~~~~~~~~
Progression.cpp:167:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |             scanf("%d %d %lld %lld", &a, &b, &c, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  174 |             scanf("%d %d %lld %lld", &a, &b, &c, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:182:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  182 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 64504 KB Output is correct
2 Correct 217 ms 2936 KB Output is correct
3 Correct 224 ms 2936 KB Output is correct
4 Correct 215 ms 2936 KB Output is correct
5 Correct 219 ms 3012 KB Output is correct
6 Correct 217 ms 3164 KB Output is correct
7 Correct 219 ms 2936 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 706 ms 64592 KB Output is correct
12 Correct 713 ms 64436 KB Output is correct
13 Correct 744 ms 64836 KB Output is correct
14 Correct 716 ms 64760 KB Output is correct
15 Correct 716 ms 64888 KB Output is correct
16 Correct 709 ms 64632 KB Output is correct
17 Correct 710 ms 64504 KB Output is correct
18 Correct 720 ms 64508 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 64876 KB Output is correct
2 Correct 180 ms 3012 KB Output is correct
3 Correct 158 ms 3068 KB Output is correct
4 Correct 145 ms 3192 KB Output is correct
5 Correct 179 ms 3192 KB Output is correct
6 Correct 178 ms 3244 KB Output is correct
7 Correct 172 ms 3192 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 849 ms 64268 KB Output is correct
12 Correct 752 ms 65144 KB Output is correct
13 Correct 833 ms 64232 KB Output is correct
14 Correct 833 ms 64152 KB Output is correct
15 Correct 747 ms 64992 KB Output is correct
16 Correct 848 ms 65072 KB Output is correct
17 Correct 828 ms 65016 KB Output is correct
18 Correct 840 ms 65144 KB Output is correct
19 Correct 770 ms 64420 KB Output is correct
20 Correct 756 ms 64380 KB Output is correct
21 Correct 753 ms 63224 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 60432 KB Output is correct
2 Correct 232 ms 660 KB Output is correct
3 Correct 235 ms 504 KB Output is correct
4 Correct 230 ms 632 KB Output is correct
5 Correct 242 ms 504 KB Output is correct
6 Correct 238 ms 504 KB Output is correct
7 Correct 239 ms 760 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1123 ms 60612 KB Output is correct
12 Correct 1151 ms 60420 KB Output is correct
13 Correct 1157 ms 60536 KB Output is correct
14 Correct 1162 ms 60796 KB Output is correct
15 Correct 1070 ms 60664 KB Output is correct
16 Correct 1193 ms 60536 KB Output is correct
17 Correct 1230 ms 60536 KB Output is correct
18 Correct 1205 ms 60376 KB Output is correct
19 Correct 1133 ms 60408 KB Output is correct
20 Correct 1138 ms 60408 KB Output is correct
21 Correct 1169 ms 60408 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 64876 KB Output is correct
2 Correct 180 ms 3012 KB Output is correct
3 Correct 158 ms 3068 KB Output is correct
4 Correct 145 ms 3192 KB Output is correct
5 Correct 179 ms 3192 KB Output is correct
6 Correct 178 ms 3244 KB Output is correct
7 Correct 172 ms 3192 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 849 ms 64268 KB Output is correct
12 Correct 752 ms 65144 KB Output is correct
13 Correct 833 ms 64232 KB Output is correct
14 Correct 833 ms 64152 KB Output is correct
15 Correct 747 ms 64992 KB Output is correct
16 Correct 848 ms 65072 KB Output is correct
17 Correct 828 ms 65016 KB Output is correct
18 Correct 840 ms 65144 KB Output is correct
19 Correct 770 ms 64420 KB Output is correct
20 Correct 756 ms 64380 KB Output is correct
21 Correct 753 ms 63224 KB Output is correct
22 Incorrect 1201 ms 60624 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 64504 KB Output is correct
2 Correct 217 ms 2936 KB Output is correct
3 Correct 224 ms 2936 KB Output is correct
4 Correct 215 ms 2936 KB Output is correct
5 Correct 219 ms 3012 KB Output is correct
6 Correct 217 ms 3164 KB Output is correct
7 Correct 219 ms 2936 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 706 ms 64592 KB Output is correct
12 Correct 713 ms 64436 KB Output is correct
13 Correct 744 ms 64836 KB Output is correct
14 Correct 716 ms 64760 KB Output is correct
15 Correct 716 ms 64888 KB Output is correct
16 Correct 709 ms 64632 KB Output is correct
17 Correct 710 ms 64504 KB Output is correct
18 Correct 720 ms 64508 KB Output is correct
19 Incorrect 3 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -