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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxSn=1e6+6;
struct Stack{
int sta[MaxSn],Top;
inline void init(){
memset(sta,0,sizeof(sta));
Top=0;
}
inline void push(int x){sta[++Top]=x;}
inline int top(){return sta[Top];}
inline void pop(){--Top;}
};
struct Pair{
int x,y;
inline bool operator <(const Pair a)const{
if(x!=a.x)return x<a.x;
return y<a.y;
}
inline bool operator ==(const Pair a)const{
return x==a.x and y==a.y;
}
inline bool operator >(const Pair a)const{
if(x!=a.x)return x>a.x;
return y>a.y;
}
inline bool operator !=(const Pair a)const{
return x!=a.x or y!=a.y;
}
};
inline Pair MakePair(int x,int y){Pair tmp;tmp.x=x,tmp.y=y;return tmp;}
const int MaxQn=262144;
const int Mod=262143;
struct Queue{
int q[MaxQn],head,tail;
inline void init(){
head=262141,tail=262141;
memset(q,0,sizeof(q));
}
inline bool empty(){return head==tail;}
inline int getNext(int x){return (x+1)&Mod;}
inline void push(int x){
q[tail]=x;
tail=getNext(tail);
}
inline int front(){return q[head];}
inline void pop(){head=getNext(head);}
};
struct frac{
ll num,den;
frac(ll num=0,ll den=1){
if(den<0){
num=-num;
den=-den;
}
assert(den!=0);
ll g=__gcd(abs(num),den);
this->num=num/g;
this->den=den/g;
}
frac init(int _n,int _d){num=_n,den=_d;}
frac init0(){num=0,den=1;}
frac init1(){num=1,den=1;}
frac operator +(const frac &o)const{return frac(num*o.den+den*o.num,den*o.den);}
frac operator -(const frac &o)const{return frac(num*o.den-den*o.num,den*o.den);}
frac operator *(const frac &o)const{return frac(num*o.num,den*o.den);}
frac operator /(const frac &o)const{return frac(num*o.den,den*o.num);}
bool operator <(const frac &o)const{return num*o.den<den*o.num;}
bool operator >(const frac &o)const{return num*o.den>den*o.num;}
bool operator ==(const frac &o)const{return num*o.den==den*o.num;}
bool operator !=(const frac &o)const{return num*o.den!=den*o.num;}
bool operator =(const frac &o){den=o.den,num=o.num;return 1;}
void print(){printf("%d/%d",num,den);}
void println(){printf("%d/%d\n",num,den);}
void printspace(){printf("%d/%d ",num,den);}
void read(){scanf("%I64d/%I64d",&num,&den);}
};
template<class T>
class Vector{
private:
T* data;
int len;
int size;
public:
Vector(){
data=NULL;
len=size=0;
}
void clear(){
data=NULL;
len=size=0;
}
Vector(int _len){
data=new T[_len];
len=_len;
size=0;
}
T& operator[](int index){return data[index];}
const Vector& push_back(const T tmp){
if(size>=len){
T* newData=new T[len*2+1];
memcpy(newData,data,len*sizeof(T));
delete []data;
data=newData;
len=2*len+1;
}
data[size++]=tmp;
return *this;
}
int getSize(){return size;}
};
|