Submission #960328

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
960328	2024-04-10 09:20:32	vjudge1	Progression (NOI20_progression)	C++17	100 / 100	1470 ms	126268 KiB

Progression

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define int long long
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();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

Progression.cpp: In function 'long long int lcq(node*, long long int, long long int, long long int)':
Progression.cpp:34:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     if(l+r>>1<pos)
      |        ~^~
Progression.cpp:35:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         return lcq(rt->rc,l+r+2>>1,r,pos);
      |                           ~~~^~
Progression.cpp:36:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     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:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     lcua(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     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:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     lcus(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     lcus(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In constructor 'tp2::tp2(tp2, tp2)':
Progression.cpp:61:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |         fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp:62:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         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:90:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                           ~^~
Progression.cpp:90:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     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:97:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     segua(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:98:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     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:106:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     segus(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:107:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |     segus(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17