oj.uz

Submission #284269

# Submission time Handle Problem Language Result Execution time Memory
284269 2020-08-27T06:31:26 Z 문홍윤(#5761) Progression (NOI20_progression) C++17
55 / 100
 1200 ms 62648 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;
            }
            tree[point].lzy=0;
            tree[point].setz=false;
        }
        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;
        }
    }
    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;
            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);
            if(tree[point].setz)return {tree[point].lzy, tree[point].lzy, e-s+1, e-s+1, e-s+1, e-s+1};
            return {tree[point].lzy+tree[point].l, tree[point].lzy+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:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Progression.cpp:158:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |     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 727 ms 61560 KB Output is correct
2 Correct 221 ms 1016 KB Output is correct
3 Correct 218 ms 1272 KB Output is correct
4 Correct 220 ms 1024 KB Output is correct
5 Correct 235 ms 1272 KB Output is correct
6 Correct 220 ms 1272 KB Output is correct
7 Correct 219 ms 1016 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 712 ms 61612 KB Output is correct
12 Correct 718 ms 61560 KB Output is correct
13 Correct 756 ms 61816 KB Output is correct
14 Correct 743 ms 61816 KB Output is correct
15 Correct 710 ms 61816 KB Output is correct
16 Correct 701 ms 61476 KB Output is correct
17 Correct 718 ms 61560 KB Output is correct
18 Correct 714 ms 61436 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 745 ms 62120 KB Output is correct
2 Correct 176 ms 1528 KB Output is correct
3 Correct 161 ms 1404 KB Output is correct
4 Correct 139 ms 1404 KB Output is correct
5 Correct 180 ms 1464 KB Output is correct
6 Correct 173 ms 1400 KB Output is correct
7 Correct 186 ms 1528 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 827 ms 61888 KB Output is correct
12 Correct 777 ms 62224 KB Output is correct
13 Correct 815 ms 62072 KB Output is correct
14 Correct 843 ms 61944 KB Output is correct
15 Correct 734 ms 62200 KB Output is correct
16 Correct 842 ms 62456 KB Output is correct
17 Correct 846 ms 62560 KB Output is correct
18 Correct 842 ms 62648 KB Output is correct
19 Correct 744 ms 61744 KB Output is correct
20 Correct 742 ms 61688 KB Output is correct
21 Correct 752 ms 61688 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1141 ms 61176 KB Output is correct
2 Correct 241 ms 632 KB Output is correct
3 Correct 255 ms 768 KB Output is correct
4 Correct 245 ms 632 KB Output is correct
5 Correct 249 ms 784 KB Output is correct
6 Correct 241 ms 624 KB Output is correct
7 Correct 255 ms 644 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 1176 ms 60920 KB Output is correct
12 Correct 1145 ms 60868 KB Output is correct
13 Correct 1164 ms 60920 KB Output is correct
14 Correct 1156 ms 61048 KB Output is correct
15 Correct 1072 ms 60796 KB Output is correct
16 Correct 1191 ms 61048 KB Output is correct
17 Correct 1170 ms 60840 KB Output is correct
18 Correct 1188 ms 60776 KB Output is correct
19 Correct 1099 ms 60920 KB Output is correct
20 Correct 1122 ms 60920 KB Output is correct
21 Correct 1146 ms 60792 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 62120 KB Output is correct
2 Correct 176 ms 1528 KB Output is correct
3 Correct 161 ms 1404 KB Output is correct
4 Correct 139 ms 1404 KB Output is correct
5 Correct 180 ms 1464 KB Output is correct
6 Correct 173 ms 1400 KB Output is correct
7 Correct 186 ms 1528 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 827 ms 61888 KB Output is correct
12 Correct 777 ms 62224 KB Output is correct
13 Correct 815 ms 62072 KB Output is correct
14 Correct 843 ms 61944 KB Output is correct
15 Correct 734 ms 62200 KB Output is correct
16 Correct 842 ms 62456 KB Output is correct
17 Correct 846 ms 62560 KB Output is correct
18 Correct 842 ms 62648 KB Output is correct
19 Correct 744 ms 61744 KB Output is correct
20 Correct 742 ms 61688 KB Output is correct
21 Correct 752 ms 61688 KB Output is correct
22 Incorrect 1200 ms 61304 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 61560 KB Output is correct
2 Correct 221 ms 1016 KB Output is correct
3 Correct 218 ms 1272 KB Output is correct
4 Correct 220 ms 1024 KB Output is correct
5 Correct 235 ms 1272 KB Output is correct
6 Correct 220 ms 1272 KB Output is correct
7 Correct 219 ms 1016 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 712 ms 61612 KB Output is correct
12 Correct 718 ms 61560 KB Output is correct
13 Correct 756 ms 61816 KB Output is correct
14 Correct 743 ms 61816 KB Output is correct
15 Correct 710 ms 61816 KB Output is correct
16 Correct 701 ms 61476 KB Output is correct
17 Correct 718 ms 61560 KB Output is correct
18 Correct 714 ms 61436 KB Output is correct
19 Incorrect 3 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -