oj.uz

Submission #960335

# Submission time Handle Problem Language Result Execution time Memory
960335 2024-04-10T09:23:59 Z boyliguanhan Progression (NOI20_progression) C++17
100 / 100
 1422 ms 125200 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
int Q=1e18;
struct Ln{
    int k,b;
    Ln(){k=b=0;}
    Ln(int x,int y){k=x,b=y;}
    friend Ln ad(Ln a, Ln b){return Ln(a.k+b.k,a.b+b.b);}
    int operator()(int x){
        return k*x+b;
    }
};
struct node{
    Ln V,S,A;
    node*lc,*rc;
    node(){A=Ln(),S=Ln(Q,0),lc=rc=0;}
    void mc(){
        if(!lc)lc=new node();
        if(!rc)rc=new node();
    }
    void push(){
        if(S.k!=Q) if(lc)
            lc->A=rc->A=Ln(),lc->S=rc->S=S,S.k=Q;
        if(A.k||A.b) if(lc)
            lc->A=ad(A,lc->A),rc->A=ad(A,rc->A),A=Ln();
    }
}*rt;
int lcq(node*rt,int l,int r,int pos){
    if(l-r) rt->mc();
    if(l==r)
        return ad(rt->A,rt->S)(pos);
    rt->push();
    if(l+r>>1<pos)
        return lcq(rt->rc,l+r+2>>1,r,pos);
    return lcq(rt->lc,l,l+r>>1,pos);
}
void lcua(node*rt,int l,int r,int tl,int tr,Ln x){
    if(l-r) rt->mc();
    if(l>tr||tl>r) return;
    if(tl<=l&&r<=tr)
        return rt->A=ad(rt->A,x),(l-r?rt->push():void());
    rt->push();
    lcua(rt->lc,l,l+r>>1,tl,tr,x);
    lcua(rt->rc,l+r+2>>1,r,tl,tr,x);
}
void lcus(node*rt,int l,int r,int tl,int tr,Ln x){
    if(l-r) rt->mc();
    if(l>tr||tl>r) return;
    if(tl<=l&&r<=tr)
        return rt->S=x,rt->A=Ln(),(l-r?rt->push():void());
    rt->push();
    lcus(rt->lc,l,l+r>>1,tl,tr,x);
    lcus(rt->rc,l+r+2>>1,r,tl,tr,x);
}
struct tp2{
    int FE,LE,ans,fans,lans,sz;
    tp2(int V,int s){FE=LE=V,ans=fans=lans=sz=s;}
    tp2(tp2 a,tp2 b){
        FE=(a.sz?a.FE:b.FE),LE=(b.sz?b.LE:a.LE);
        fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans);
        lans=(b.ans==b.sz&&LE==a.LE||!b.sz?b.sz+a.lans:b.lans);
        ans=max({a.ans,b.ans,(a.LE==b.FE)*(a.lans+b.fans)});
        sz=a.sz+b.sz;
    }
};
struct node2{
    tp2 V=tp2(0ll,1ll);
    int A=0,S=Q;
    node2(int v){V=tp2(v,1ll);}
    node2(){}
} T[1<<20];
void pd(int i,bool b){
    if(T[i].S!=Q){
        T[i].V=tp2(T[i].S,T[i].V.sz); if(b)
        T[i*2].S=T[i*2+1].S=T[i].S,T[i*2].A=T[i*2+1].A=0;
    }
    if(T[i].A){
        T[i].V.FE+=T[i].A,T[i].V.LE+=T[i].A; if(b)
        T[i*2].A+=T[i].A,T[i*2+1].A+=T[i].A;
    }
    T[i].A=0,T[i].S=Q;
}
tp2 segq(int i,int l,int r,int tl,int tr){
    pd(i,l-r);
    if(tl<=l&&r<=tr)
        return T[i].V;
    if(l>tr||tl>r)
        return tp2(0,0);
    return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
}
void segua(int i,int l,int r,int tl,int tr,int X){
    pd(i,l-r);
    if(tl<=l&&r<=tr)
        return T[i].A+=X,pd(i,l-r);
    if(l>tr||tl>r) return;
    segua(i*2,l,l+r>>1,tl,tr,X);
    segua(i*2+1,l+r+2>>1,r,tl,tr,X);
    T[i].V=tp2(T[i*2].V,T[i*2+1].V);
}
void segus(int i,int l,int r,int tl,int tr,int X){
    pd(i,l-r);
    if(tl<=l&&r<=tr)
        return T[i].A=0,T[i].S=X,pd(i,l-r);
    if(l>tr||tl>r) return;
    segus(i*2,l,l+r>>1,tl,tr,X);
    segus(i*2+1,l+r+2>>1,r,tl,tr,X);
    T[i].V=tp2(T[i*2].V,T[i*2+1].V);
}
int bruh[5<<16],n;
void maintain(int id){
    segus(1,1,n-1,id,id,lcq(rt,1,n,id+1)-lcq(rt,1,n,id));
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int m;
    rt=new node();
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>bruh[i];
        lcus(rt,1,n,i,i,Ln(0,bruh[i]));
    }
    for(int i=1;i<n;i++)
        segus(1,1,n-1,i,i,bruh[i+1]-bruh[i]);
    while(m--){
        int t,l,r,s,c;
        cin>>t>>l>>r;
        if(t>2){
            cout<<(n-1?segq(1,1,n-1,l,r-1).ans+1:1)<<'\n';
            continue;
        }
        cin>>s>>c;
        if(t<2){
            lcua(rt,1,n,l,r,Ln(c,s-l*c));
            segua(1,1,n-1,l,r-1,c);
        } else {
            lcus(rt,1,n,l,r,Ln(c,s-l*c));
            segus(1,1,n-1,l,r-1,c);
        }
        if(l>1) maintain(l-1);
        if(r<n) maintain(r);
    }
}

Compilation message

Progression.cpp: In function 'long long int lcq(node*, long long int, long long int, long long int)':
Progression.cpp:35:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     if(l+r>>1<pos)
      |        ~^~
Progression.cpp:36:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         return lcq(rt->rc,l+r+2>>1,r,pos);
      |                           ~~~^~
Progression.cpp:37:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     return lcq(rt->lc,l,l+r>>1,pos);
      |                         ~^~
Progression.cpp: In function 'void lcua(node*, long long int, long long int, long long int, long long int, Ln)':
Progression.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     lcua(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     lcua(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In function 'void lcus(node*, long long int, long long int, long long int, long long int, Ln)':
Progression.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     lcus(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     lcus(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In constructor 'tp2::tp2(tp2, tp2)':
Progression.cpp:62:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp:63:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   63 |         lans=(b.ans==b.sz&&LE==a.LE||!b.sz?b.sz+a.lans:b.lans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp: In function 'tp2 segq(long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:91:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                           ~^~
Progression.cpp:91:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                                                    ~~~^~
Progression.cpp: In function 'void segua(long long int, long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     segua(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:99:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     segua(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~
Progression.cpp: In function 'void segus(long long int, long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:107:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |     segus(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:108:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     segus(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 123404 KB Output is correct
2 Correct 80 ms 69408 KB Output is correct
3 Correct 89 ms 69416 KB Output is correct
4 Correct 77 ms 69396 KB Output is correct
5 Correct 75 ms 69496 KB Output is correct
6 Correct 78 ms 69460 KB Output is correct
7 Correct 81 ms 69312 KB Output is correct
8 Correct 15 ms 66392 KB Output is correct
9 Correct 16 ms 66396 KB Output is correct
10 Correct 11 ms 66396 KB Output is correct
11 Correct 318 ms 122800 KB Output is correct
12 Correct 277 ms 122816 KB Output is correct
13 Correct 280 ms 123056 KB Output is correct
14 Correct 317 ms 123116 KB Output is correct
15 Correct 287 ms 122684 KB Output is correct
16 Correct 286 ms 122960 KB Output is correct
17 Correct 305 ms 122820 KB Output is correct
18 Correct 271 ms 122704 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 66648 KB Output is correct
2 Correct 17 ms 66248 KB Output is correct
3 Correct 14 ms 66284 KB Output is correct
4 Correct 15 ms 66260 KB Output is correct
5 Correct 14 ms 66392 KB Output is correct
6 Correct 16 ms 66396 KB Output is correct
7 Correct 15 ms 66392 KB Output is correct
8 Correct 18 ms 66392 KB Output is correct
9 Correct 16 ms 66600 KB Output is correct
10 Correct 16 ms 66392 KB Output is correct
11 Correct 16 ms 66608 KB Output is correct
12 Correct 16 ms 66648 KB Output is correct
13 Correct 15 ms 66652 KB Output is correct
14 Correct 15 ms 66652 KB Output is correct
15 Correct 16 ms 66652 KB Output is correct
16 Correct 12 ms 66652 KB Output is correct
17 Correct 16 ms 66528 KB Output is correct
18 Correct 15 ms 66604 KB Output is correct
19 Correct 16 ms 66392 KB Output is correct
20 Correct 15 ms 66396 KB Output is correct
21 Correct 16 ms 66396 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 122156 KB Output is correct
2 Correct 95 ms 68944 KB Output is correct
3 Correct 93 ms 68916 KB Output is correct
4 Correct 84 ms 69012 KB Output is correct
5 Correct 92 ms 69200 KB Output is correct
6 Correct 91 ms 69144 KB Output is correct
7 Correct 93 ms 69152 KB Output is correct
8 Correct 19 ms 66392 KB Output is correct
9 Correct 21 ms 66440 KB Output is correct
10 Correct 11 ms 66472 KB Output is correct
11 Correct 429 ms 120704 KB Output is correct
12 Correct 406 ms 121840 KB Output is correct
13 Correct 420 ms 120664 KB Output is correct
14 Correct 440 ms 121148 KB Output is correct
15 Correct 408 ms 121720 KB Output is correct
16 Correct 432 ms 122236 KB Output is correct
17 Correct 433 ms 122380 KB Output is correct
18 Correct 426 ms 122424 KB Output is correct
19 Correct 428 ms 121784 KB Output is correct
20 Correct 381 ms 121572 KB Output is correct
21 Correct 428 ms 121712 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 125200 KB Output is correct
2 Correct 170 ms 69556 KB Output is correct
3 Correct 166 ms 69576 KB Output is correct
4 Correct 168 ms 69780 KB Output is correct
5 Correct 156 ms 69636 KB Output is correct
6 Correct 163 ms 69724 KB Output is correct
7 Correct 162 ms 69728 KB Output is correct
8 Correct 13 ms 66260 KB Output is correct
9 Correct 11 ms 66476 KB Output is correct
10 Correct 11 ms 66236 KB Output is correct
11 Correct 1012 ms 122460 KB Output is correct
12 Correct 967 ms 123736 KB Output is correct
13 Correct 932 ms 121580 KB Output is correct
14 Correct 949 ms 121012 KB Output is correct
15 Correct 936 ms 123708 KB Output is correct
16 Correct 1004 ms 123640 KB Output is correct
17 Correct 955 ms 123872 KB Output is correct
18 Correct 966 ms 123936 KB Output is correct
19 Correct 954 ms 123872 KB Output is correct
20 Correct 924 ms 123616 KB Output is correct
21 Correct 939 ms 123588 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 122156 KB Output is correct
2 Correct 95 ms 68944 KB Output is correct
3 Correct 93 ms 68916 KB Output is correct
4 Correct 84 ms 69012 KB Output is correct
5 Correct 92 ms 69200 KB Output is correct
6 Correct 91 ms 69144 KB Output is correct
7 Correct 93 ms 69152 KB Output is correct
8 Correct 19 ms 66392 KB Output is correct
9 Correct 21 ms 66440 KB Output is correct
10 Correct 11 ms 66472 KB Output is correct
11 Correct 429 ms 120704 KB Output is correct
12 Correct 406 ms 121840 KB Output is correct
13 Correct 420 ms 120664 KB Output is correct
14 Correct 440 ms 121148 KB Output is correct
15 Correct 408 ms 121720 KB Output is correct
16 Correct 432 ms 122236 KB Output is correct
17 Correct 433 ms 122380 KB Output is correct
18 Correct 426 ms 122424 KB Output is correct
19 Correct 428 ms 121784 KB Output is correct
20 Correct 381 ms 121572 KB Output is correct
21 Correct 428 ms 121712 KB Output is correct
22 Correct 1163 ms 123376 KB Output is correct
23 Correct 173 ms 69204 KB Output is correct
24 Correct 167 ms 69352 KB Output is correct
25 Correct 164 ms 69272 KB Output is correct
26 Correct 163 ms 69588 KB Output is correct
27 Correct 163 ms 69384 KB Output is correct
28 Correct 165 ms 69676 KB Output is correct
29 Correct 10 ms 66404 KB Output is correct
30 Correct 11 ms 66296 KB Output is correct
31 Correct 11 ms 66396 KB Output is correct
32 Correct 1207 ms 121180 KB Output is correct
33 Correct 1147 ms 123528 KB Output is correct
34 Correct 1158 ms 121392 KB Output is correct
35 Correct 1195 ms 121176 KB Output is correct
36 Correct 870 ms 121024 KB Output is correct
37 Correct 869 ms 120988 KB Output is correct
38 Correct 841 ms 120996 KB Output is correct
39 Correct 1125 ms 123316 KB Output is correct
40 Correct 1170 ms 123448 KB Output is correct
41 Correct 1170 ms 123608 KB Output is correct
42 Correct 1174 ms 123452 KB Output is correct
43 Correct 1122 ms 123396 KB Output is correct
44 Correct 1146 ms 121456 KB Output is correct
45 Correct 1133 ms 120624 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 123404 KB Output is correct
2 Correct 80 ms 69408 KB Output is correct
3 Correct 89 ms 69416 KB Output is correct
4 Correct 77 ms 69396 KB Output is correct
5 Correct 75 ms 69496 KB Output is correct
6 Correct 78 ms 69460 KB Output is correct
7 Correct 81 ms 69312 KB Output is correct
8 Correct 15 ms 66392 KB Output is correct
9 Correct 16 ms 66396 KB Output is correct
10 Correct 11 ms 66396 KB Output is correct
11 Correct 318 ms 122800 KB Output is correct
12 Correct 277 ms 122816 KB Output is correct
13 Correct 280 ms 123056 KB Output is correct
14 Correct 317 ms 123116 KB Output is correct
15 Correct 287 ms 122684 KB Output is correct
16 Correct 286 ms 122960 KB Output is correct
17 Correct 305 ms 122820 KB Output is correct
18 Correct 271 ms 122704 KB Output is correct
19 Correct 21 ms 66648 KB Output is correct
20 Correct 17 ms 66248 KB Output is correct
21 Correct 14 ms 66284 KB Output is correct
22 Correct 15 ms 66260 KB Output is correct
23 Correct 14 ms 66392 KB Output is correct
24 Correct 16 ms 66396 KB Output is correct
25 Correct 15 ms 66392 KB Output is correct
26 Correct 18 ms 66392 KB Output is correct
27 Correct 16 ms 66600 KB Output is correct
28 Correct 16 ms 66392 KB Output is correct
29 Correct 16 ms 66608 KB Output is correct
30 Correct 16 ms 66648 KB Output is correct
31 Correct 15 ms 66652 KB Output is correct
32 Correct 15 ms 66652 KB Output is correct
33 Correct 16 ms 66652 KB Output is correct
34 Correct 12 ms 66652 KB Output is correct
35 Correct 16 ms 66528 KB Output is correct
36 Correct 15 ms 66604 KB Output is correct
37 Correct 16 ms 66392 KB Output is correct
38 Correct 15 ms 66396 KB Output is correct
39 Correct 16 ms 66396 KB Output is correct
40 Correct 419 ms 122156 KB Output is correct
41 Correct 95 ms 68944 KB Output is correct
42 Correct 93 ms 68916 KB Output is correct
43 Correct 84 ms 69012 KB Output is correct
44 Correct 92 ms 69200 KB Output is correct
45 Correct 91 ms 69144 KB Output is correct
46 Correct 93 ms 69152 KB Output is correct
47 Correct 19 ms 66392 KB Output is correct
48 Correct 21 ms 66440 KB Output is correct
49 Correct 11 ms 66472 KB Output is correct
50 Correct 429 ms 120704 KB Output is correct
51 Correct 406 ms 121840 KB Output is correct
52 Correct 420 ms 120664 KB Output is correct
53 Correct 440 ms 121148 KB Output is correct
54 Correct 408 ms 121720 KB Output is correct
55 Correct 432 ms 122236 KB Output is correct
56 Correct 433 ms 122380 KB Output is correct
57 Correct 426 ms 122424 KB Output is correct
58 Correct 428 ms 121784 KB Output is correct
59 Correct 381 ms 121572 KB Output is correct
60 Correct 428 ms 121712 KB Output is correct
61 Correct 991 ms 125200 KB Output is correct
62 Correct 170 ms 69556 KB Output is correct
63 Correct 166 ms 69576 KB Output is correct
64 Correct 168 ms 69780 KB Output is correct
65 Correct 156 ms 69636 KB Output is correct
66 Correct 163 ms 69724 KB Output is correct
67 Correct 162 ms 69728 KB Output is correct
68 Correct 13 ms 66260 KB Output is correct
69 Correct 11 ms 66476 KB Output is correct
70 Correct 11 ms 66236 KB Output is correct
71 Correct 1012 ms 122460 KB Output is correct
72 Correct 967 ms 123736 KB Output is correct
73 Correct 932 ms 121580 KB Output is correct
74 Correct 949 ms 121012 KB Output is correct
75 Correct 936 ms 123708 KB Output is correct
76 Correct 1004 ms 123640 KB Output is correct
77 Correct 955 ms 123872 KB Output is correct
78 Correct 966 ms 123936 KB Output is correct
79 Correct 954 ms 123872 KB Output is correct
80 Correct 924 ms 123616 KB Output is correct
81 Correct 939 ms 123588 KB Output is correct
82 Correct 1163 ms 123376 KB Output is correct
83 Correct 173 ms 69204 KB Output is correct
84 Correct 167 ms 69352 KB Output is correct
85 Correct 164 ms 69272 KB Output is correct
86 Correct 163 ms 69588 KB Output is correct
87 Correct 163 ms 69384 KB Output is correct
88 Correct 165 ms 69676 KB Output is correct
89 Correct 10 ms 66404 KB Output is correct
90 Correct 11 ms 66296 KB Output is correct
91 Correct 11 ms 66396 KB Output is correct
92 Correct 1207 ms 121180 KB Output is correct
93 Correct 1147 ms 123528 KB Output is correct
94 Correct 1158 ms 121392 KB Output is correct
95 Correct 1195 ms 121176 KB Output is correct
96 Correct 870 ms 121024 KB Output is correct
97 Correct 869 ms 120988 KB Output is correct
98 Correct 841 ms 120996 KB Output is correct
99 Correct 1125 ms 123316 KB Output is correct
100 Correct 1170 ms 123448 KB Output is correct
101 Correct 1170 ms 123608 KB Output is correct
102 Correct 1174 ms 123452 KB Output is correct
103 Correct 1122 ms 123396 KB Output is correct
104 Correct 1146 ms 121456 KB Output is correct
105 Correct 1133 ms 120624 KB Output is correct
106 Correct 1396 ms 121700 KB Output is correct
107 Correct 200 ms 68592 KB Output is correct
108 Correct 195 ms 68436 KB Output is correct
109 Correct 200 ms 68580 KB Output is correct
110 Correct 11 ms 66336 KB Output is correct
111 Correct 11 ms 66392 KB Output is correct
112 Correct 11 ms 66396 KB Output is correct
113 Correct 1150 ms 120796 KB Output is correct
114 Correct 1153 ms 120952 KB Output is correct
115 Correct 1140 ms 120800 KB Output is correct
116 Correct 1166 ms 120988 KB Output is correct
117 Correct 1417 ms 121400 KB Output is correct
118 Correct 1166 ms 120980 KB Output is correct
119 Correct 1163 ms 120712 KB Output is correct
120 Correct 439 ms 120580 KB Output is correct
121 Correct 394 ms 120608 KB Output is correct
122 Correct 421 ms 120460 KB Output is correct
123 Correct 396 ms 119904 KB Output is correct
124 Correct 375 ms 119820 KB Output is correct
125 Correct 409 ms 119992 KB Output is correct
126 Correct 1417 ms 119768 KB Output is correct
127 Correct 1374 ms 119900 KB Output is correct
128 Correct 1376 ms 121488 KB Output is correct
129 Correct 1389 ms 120028 KB Output is correct
130 Correct 961 ms 120232 KB Output is correct
131 Correct 900 ms 119988 KB Output is correct
132 Correct 935 ms 120240 KB Output is correct
133 Correct 1422 ms 121728 KB Output is correct
134 Correct 1380 ms 117316 KB Output is correct
135 Correct 1409 ms 116308 KB Output is correct
136 Correct 202 ms 66644 KB Output is correct
137 Correct 194 ms 66544 KB Output is correct
138 Correct 208 ms 66756 KB Output is correct