답안 #284259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284259	2020-08-27T05:58:06 Z	최은수(#5747)	Progression (NOI20_progression)	C++17	100 / 100	1159 ms	91212 KB

Progression

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct seg
{
    struct node
    {
        int lmx;
        ll lk,lv;
        int rmx;
        ll rk,rv;
        int mx,sz;
        node(){}
        node operator+(const node&x)const
        {
            node ret;
            ret.lv=lv;
            ret.rv=x.rv;
            ret.sz=sz+x.sz;
            ret.mx=max({mx,x.mx,2});
            {
                bool f1=rk==x.lv-rv;
                bool f2=x.lk==x.lv-rv;
                if(f1)
                {
                    if(f2)
                        ret.mx=max(ret.mx,rmx+x.lmx);
                    else
                        ret.mx=max(ret.mx,rmx+1);
                }
                else if(f2)
                    ret.mx=max(ret.mx,1+x.lmx);
            }
            {
                if(lmx==sz)
                {
                    if(sz==1||x.lv-rv==lk)
                    {
                        ret.lk=x.lv-rv;
                        if(ret.lk==x.lk)
                            ret.lmx=lmx+x.lmx;
                        else
                            ret.lmx=lmx+1;
                    }
                    else
                        ret.lmx=lmx,ret.lk=lk;
                }
                else
                    ret.lmx=lmx,ret.lk=lk;
            }
            {
                if(x.rmx==x.sz)
                {
                    if(x.sz==1||x.lv-rv==x.rk)
                    {
                        ret.rk=x.lv-rv;
                        if(ret.rk==rk)
                            ret.rmx=x.rmx+rmx;
                        else
                            ret.rmx=x.rmx+1;
                    }
                    else
                        ret.rmx=x.rmx,ret.rk=x.rk;
                }
                else
                    ret.rmx=x.rmx,ret.rk=x.rk;
            }
            return ret;
        }
    }t[1200010];
    int la[1200010];
    ll lb[1200010],lc[1200010];
    void init(int n,int s,int e,vector<ll>&v)
    {
        la[n]=1,lb[n]=lc[n]=0;
        if(s==e)
        {
            t[n].lv=t[n].rv=v[s];
            t[n].lmx=t[n].rmx=t[n].mx=t[n].sz=1;
            t[n].lk=t[n].rk=0;
            return;
        }
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        t[n]=t[n*2]+t[n*2+1];
        return;
    }
    inline void put(int n,int s,int e,int a,ll b,ll c)
    {
        if(a==0)
        {
            t[n].lk=b,t[n].rk=b;
            t[n].lv=s*b+c,t[n].rv=e*b+c;
            t[n].mx=t[n].lmx=t[n].rmx=t[n].sz;
            la[n]=0,lb[n]=b,lc[n]=c;
        }
        else
        {
            t[n].lk+=b,t[n].rk+=b;
            t[n].lv+=s*b+c,t[n].rv+=e*b+c;
            lb[n]+=b,lc[n]+=c;
        }
        return;
    }
    inline void prop(int n,int s,int e,int m)
    {
        if(la[n]==1&&lb[n]==0&&lc[n]==0)
            return;
        put(n*2,s,m,la[n],lb[n],lc[n]);
        put(n*2+1,m+1,e,la[n],lb[n],lc[n]);
        la[n]=1;
        lb[n]=lc[n]=0;
        return;
    }
    int S,E;
    int ca;
    ll cb,cc;
    void upd(int n,int s,int e)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
            return put(n,s,e,ca,cb,cc);
        int m=s+(e-s)/2;
        prop(n,s,e,m);
        upd(n*2,s,m);
        upd(n*2+1,m+1,e);
        t[n]=t[n*2]+t[n*2+1];
        return;
    }
    node query(int n,int s,int e)
    {
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        prop(n,s,e,m);
        if(E<=m)
            return query(n*2,s,m);
        if(S>m)
            return query(n*2+1,m+1,e);
        return query(n*2,s,m)+query(n*2+1,m+1,e);
    }
}st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<ll>v(n);
    for(ll&t:v)
        cin>>t;
    v.insert(v.begin(),0);
    st.init(1,1,n,v);
    for(int qi=0;qi<q;qi++)
    {
        int t;
        cin>>t>>st.S>>st.E;
        if(t==1)
            cin>>st.cc>>st.cb,st.cc-=st.cb*st.S,st.ca=1,st.upd(1,1,n);
        else if(t==2)
            cin>>st.cc>>st.cb,st.cc-=st.cb*st.S,st.ca=0,st.upd(1,1,n);
        else
            cout<<st.query(1,1,n).mx<<'\n';
    }
    return 0;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	205 ms	89292 KB	Output is correct
2	Correct	105 ms	3576 KB	Output is correct
3	Correct	123 ms	3600 KB	Output is correct
4	Correct	101 ms	3576 KB	Output is correct
5	Correct	102 ms	3832 KB	Output is correct
6	Correct	108 ms	3704 KB	Output is correct
7	Correct	101 ms	3576 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	199 ms	89472 KB	Output is correct
12	Correct	206 ms	89292 KB	Output is correct
13	Correct	198 ms	89676 KB	Output is correct
14	Correct	203 ms	89676 KB	Output is correct
15	Correct	204 ms	89548 KB	Output is correct
16	Correct	214 ms	89292 KB	Output is correct
17	Correct	223 ms	89292 KB	Output is correct
18	Correct	203 ms	89292 KB	Output is correct

Subtask #2

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	412 KB	Output is correct
8	Correct	2 ms	512 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	2 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	2 ms	512 KB	Output is correct
18	Correct	2 ms	512 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct

Subtask #3

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	345 ms	87892 KB	Output is correct
2	Correct	99 ms	3064 KB	Output is correct
3	Correct	103 ms	3052 KB	Output is correct
4	Correct	95 ms	3064 KB	Output is correct
5	Correct	99 ms	3320 KB	Output is correct
6	Correct	100 ms	3192 KB	Output is correct
7	Correct	102 ms	3320 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	417 ms	86384 KB	Output is correct
12	Correct	334 ms	87888 KB	Output is correct
13	Correct	425 ms	86472 KB	Output is correct
14	Correct	420 ms	86600 KB	Output is correct
15	Correct	333 ms	87888 KB	Output is correct
16	Correct	413 ms	88524 KB	Output is correct
17	Correct	422 ms	88272 KB	Output is correct
18	Correct	417 ms	88396 KB	Output is correct
19	Correct	348 ms	87756 KB	Output is correct
20	Correct	367 ms	87756 KB	Output is correct
21	Correct	352 ms	87884 KB	Output is correct

Subtask #4

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	603 ms	90572 KB	Output is correct
2	Correct	139 ms	3728 KB	Output is correct
3	Correct	141 ms	3836 KB	Output is correct
4	Correct	129 ms	3708 KB	Output is correct
5	Correct	133 ms	3704 KB	Output is correct
6	Correct	132 ms	3708 KB	Output is correct
7	Correct	129 ms	3852 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	611 ms	87496 KB	Output is correct
12	Correct	597 ms	90648 KB	Output is correct
13	Correct	630 ms	87500 KB	Output is correct
14	Correct	615 ms	87444 KB	Output is correct
15	Correct	588 ms	90644 KB	Output is correct
16	Correct	613 ms	90808 KB	Output is correct
17	Correct	623 ms	90824 KB	Output is correct
18	Correct	639 ms	91004 KB	Output is correct
19	Correct	620 ms	90612 KB	Output is correct
20	Correct	616 ms	90700 KB	Output is correct
21	Correct	640 ms	90620 KB	Output is correct

Subtask #5

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	345 ms	87892 KB	Output is correct
2	Correct	99 ms	3064 KB	Output is correct
3	Correct	103 ms	3052 KB	Output is correct
4	Correct	95 ms	3064 KB	Output is correct
5	Correct	99 ms	3320 KB	Output is correct
6	Correct	100 ms	3192 KB	Output is correct
7	Correct	102 ms	3320 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	417 ms	86384 KB	Output is correct
12	Correct	334 ms	87888 KB	Output is correct
13	Correct	425 ms	86472 KB	Output is correct
14	Correct	420 ms	86600 KB	Output is correct
15	Correct	333 ms	87888 KB	Output is correct
16	Correct	413 ms	88524 KB	Output is correct
17	Correct	422 ms	88272 KB	Output is correct
18	Correct	417 ms	88396 KB	Output is correct
19	Correct	348 ms	87756 KB	Output is correct
20	Correct	367 ms	87756 KB	Output is correct
21	Correct	352 ms	87884 KB	Output is correct
22	Correct	903 ms	90256 KB	Output is correct
23	Correct	132 ms	3576 KB	Output is correct
24	Correct	131 ms	3576 KB	Output is correct
25	Correct	136 ms	3744 KB	Output is correct
26	Correct	135 ms	3832 KB	Output is correct
27	Correct	135 ms	3708 KB	Output is correct
28	Correct	133 ms	3704 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Correct	1 ms	384 KB	Output is correct
32	Correct	929 ms	87496 KB	Output is correct
33	Correct	882 ms	90188 KB	Output is correct
34	Correct	932 ms	87244 KB	Output is correct
35	Correct	1002 ms	87372 KB	Output is correct
36	Correct	856 ms	87116 KB	Output is correct
37	Correct	813 ms	87244 KB	Output is correct
38	Correct	788 ms	87248 KB	Output is correct
39	Correct	912 ms	90188 KB	Output is correct
40	Correct	1000 ms	90312 KB	Output is correct
41	Correct	957 ms	90360 KB	Output is correct
42	Correct	967 ms	90056 KB	Output is correct
43	Correct	908 ms	90128 KB	Output is correct
44	Correct	942 ms	90088 KB	Output is correct
45	Correct	946 ms	90292 KB	Output is correct

Subtask #6

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	205 ms	89292 KB	Output is correct
2	Correct	105 ms	3576 KB	Output is correct
3	Correct	123 ms	3600 KB	Output is correct
4	Correct	101 ms	3576 KB	Output is correct
5	Correct	102 ms	3832 KB	Output is correct
6	Correct	108 ms	3704 KB	Output is correct
7	Correct	101 ms	3576 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	199 ms	89472 KB	Output is correct
12	Correct	206 ms	89292 KB	Output is correct
13	Correct	198 ms	89676 KB	Output is correct
14	Correct	203 ms	89676 KB	Output is correct
15	Correct	204 ms	89548 KB	Output is correct
16	Correct	214 ms	89292 KB	Output is correct
17	Correct	223 ms	89292 KB	Output is correct
18	Correct	203 ms	89292 KB	Output is correct
19	Correct	2 ms	512 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	412 KB	Output is correct
26	Correct	2 ms	512 KB	Output is correct
27	Correct	2 ms	640 KB	Output is correct
28	Correct	2 ms	512 KB	Output is correct
29	Correct	2 ms	512 KB	Output is correct
30	Correct	2 ms	512 KB	Output is correct
31	Correct	1 ms	512 KB	Output is correct
32	Correct	2 ms	512 KB	Output is correct
33	Correct	2 ms	512 KB	Output is correct
34	Correct	2 ms	512 KB	Output is correct
35	Correct	2 ms	512 KB	Output is correct
36	Correct	2 ms	512 KB	Output is correct
37	Correct	1 ms	384 KB	Output is correct
38	Correct	1 ms	384 KB	Output is correct
39	Correct	1 ms	384 KB	Output is correct
40	Correct	345 ms	87892 KB	Output is correct
41	Correct	99 ms	3064 KB	Output is correct
42	Correct	103 ms	3052 KB	Output is correct
43	Correct	95 ms	3064 KB	Output is correct
44	Correct	99 ms	3320 KB	Output is correct
45	Correct	100 ms	3192 KB	Output is correct
46	Correct	102 ms	3320 KB	Output is correct
47	Correct	1 ms	384 KB	Output is correct
48	Correct	1 ms	384 KB	Output is correct
49	Correct	1 ms	384 KB	Output is correct
50	Correct	417 ms	86384 KB	Output is correct
51	Correct	334 ms	87888 KB	Output is correct
52	Correct	425 ms	86472 KB	Output is correct
53	Correct	420 ms	86600 KB	Output is correct
54	Correct	333 ms	87888 KB	Output is correct
55	Correct	413 ms	88524 KB	Output is correct
56	Correct	422 ms	88272 KB	Output is correct
57	Correct	417 ms	88396 KB	Output is correct
58	Correct	348 ms	87756 KB	Output is correct
59	Correct	367 ms	87756 KB	Output is correct
60	Correct	352 ms	87884 KB	Output is correct
61	Correct	603 ms	90572 KB	Output is correct
62	Correct	139 ms	3728 KB	Output is correct
63	Correct	141 ms	3836 KB	Output is correct
64	Correct	129 ms	3708 KB	Output is correct
65	Correct	133 ms	3704 KB	Output is correct
66	Correct	132 ms	3708 KB	Output is correct
67	Correct	129 ms	3852 KB	Output is correct
68	Correct	1 ms	384 KB	Output is correct
69	Correct	1 ms	384 KB	Output is correct
70	Correct	1 ms	384 KB	Output is correct
71	Correct	611 ms	87496 KB	Output is correct
72	Correct	597 ms	90648 KB	Output is correct
73	Correct	630 ms	87500 KB	Output is correct
74	Correct	615 ms	87444 KB	Output is correct
75	Correct	588 ms	90644 KB	Output is correct
76	Correct	613 ms	90808 KB	Output is correct
77	Correct	623 ms	90824 KB	Output is correct
78	Correct	639 ms	91004 KB	Output is correct
79	Correct	620 ms	90612 KB	Output is correct
80	Correct	616 ms	90700 KB	Output is correct
81	Correct	640 ms	90620 KB	Output is correct
82	Correct	903 ms	90256 KB	Output is correct
83	Correct	132 ms	3576 KB	Output is correct
84	Correct	131 ms	3576 KB	Output is correct
85	Correct	136 ms	3744 KB	Output is correct
86	Correct	135 ms	3832 KB	Output is correct
87	Correct	135 ms	3708 KB	Output is correct
88	Correct	133 ms	3704 KB	Output is correct
89	Correct	1 ms	384 KB	Output is correct
90	Correct	1 ms	384 KB	Output is correct
91	Correct	1 ms	384 KB	Output is correct
92	Correct	929 ms	87496 KB	Output is correct
93	Correct	882 ms	90188 KB	Output is correct
94	Correct	932 ms	87244 KB	Output is correct
95	Correct	1002 ms	87372 KB	Output is correct
96	Correct	856 ms	87116 KB	Output is correct
97	Correct	813 ms	87244 KB	Output is correct
98	Correct	788 ms	87248 KB	Output is correct
99	Correct	912 ms	90188 KB	Output is correct
100	Correct	1000 ms	90312 KB	Output is correct
101	Correct	957 ms	90360 KB	Output is correct
102	Correct	967 ms	90056 KB	Output is correct
103	Correct	908 ms	90128 KB	Output is correct
104	Correct	942 ms	90088 KB	Output is correct
105	Correct	946 ms	90292 KB	Output is correct
106	Correct	1096 ms	91108 KB	Output is correct
107	Correct	160 ms	3832 KB	Output is correct
108	Correct	162 ms	3832 KB	Output is correct
109	Correct	159 ms	3832 KB	Output is correct
110	Correct	1 ms	384 KB	Output is correct
111	Correct	1 ms	384 KB	Output is correct
112	Correct	1 ms	384 KB	Output is correct
113	Correct	957 ms	90444 KB	Output is correct
114	Correct	962 ms	90288 KB	Output is correct
115	Correct	974 ms	90232 KB	Output is correct
116	Correct	898 ms	90068 KB	Output is correct
117	Correct	1129 ms	91212 KB	Output is correct
118	Correct	921 ms	90060 KB	Output is correct
119	Correct	932 ms	90316 KB	Output is correct
120	Correct	419 ms	88652 KB	Output is correct
121	Correct	443 ms	88588 KB	Output is correct
122	Correct	433 ms	88656 KB	Output is correct
123	Correct	365 ms	87980 KB	Output is correct
124	Correct	351 ms	87756 KB	Output is correct
125	Correct	336 ms	87884 KB	Output is correct
126	Correct	1039 ms	87756 KB	Output is correct
127	Correct	1075 ms	87888 KB	Output is correct
128	Correct	1108 ms	91152 KB	Output is correct
129	Correct	1050 ms	87756 KB	Output is correct
130	Correct	864 ms	88012 KB	Output is correct
131	Correct	880 ms	87884 KB	Output is correct
132	Correct	861 ms	87756 KB	Output is correct
133	Correct	1159 ms	91084 KB	Output is correct
134	Correct	1116 ms	91084 KB	Output is correct
135	Correct	1074 ms	91212 KB	Output is correct
136	Correct	160 ms	3960 KB	Output is correct
137	Correct	158 ms	3832 KB	Output is correct
138	Correct	158 ms	3784 KB	Output is correct