QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670623 | #7451. TB5X | zjy0001 | 100 ✓ | 1319ms | 66188kb | C++14 | 6.0kb | 2024-10-23 22:36:25 | 2024-10-23 22:36:47 |
Judging History
answer
//gxy001
//TB5x
/* BEGIN HEADER: */
class Data {
friend class Operation;
friend int main();
private:
unsigned int x, sz, T, flag;
void read();
void print() const;
public:
Data() { clr(); }
void add_eq(const Data &a);
void add(const Data &a, const Data &b);
void clr();
bool empty() const;
};
class Operation {
friend int main();
private:
unsigned int a, b, L, R, flag;
void read();
public:
Operation() { clr(); }
void apply(Data &w) const;
void apply(Operation &w) const;
void clr();
bool empty() const;
};
void solve(const int n, const int m, const int p[], const Data d[],
const int x1[], const int x2[], const int y1[], const int y2[],
const Operation o[][3][3], Data ans[][3][3]);
/* END HEADER. */
#include<algorithm>
#include<vector>
int const B=105;
int n,cnt,X1[210],X2[210],Y1[210],Y2[210],X[100010],Y[100010];
Data tr[400010],ans[210][3][3];
Operation lz[400010],op[210][3][3];
int pool[1000010],*pl;
int *son[400010],sons[400010];
struct Vector{
int *bg,len;
void resize(int x,int y){
bg=pl,pl+=x*y,len=y;
for(int i=0;i<x;i++)for(int j=0;j<y;j++)*(bg+i*len+j)=++cnt,sons[cnt]=0;
}
int * operator [](int x){return bg+x*len;}
}vec[810];
std::pair<int,int> dool[400010],*dl;
std::pair<int,int> *x[810],*y[810];
int szx[810],szy[810];
void merge(std::pair<int,int> *a,int la,std::pair<int,int> *b,int lb,std::pair<int,int> *&ans,int &ansl){
ans=dl;
for(int i=0;i<lb;i++){
for(int j=0,l=0,r;j<la;j++,l=r+1){
r=l+a[j].second-a[j].first;
int pl=std::max(l,b[i].first),pr=std::min(r,b[i].second);
if(pl<=pr) *dl++=std::make_pair(a[j].first+pl-l,a[j].second-r+pr);
}
}
ansl=dl-ans;
}
void build(int p,int l,int r){
if(l==r){
vec[p].resize(3,3);
x[p]=dl,dl+=3,y[p]=dl,dl+=3;
x[p][0]=std::make_pair(0,X1[l]-1);
x[p][2]=std::make_pair(X1[l],X2[l]-1);
x[p][1]=std::make_pair(X2[l],n-1);
y[p][0]=std::make_pair(0,Y1[l]-1);
y[p][2]=std::make_pair(Y1[l],Y2[l]-1);
y[p][1]=std::make_pair(Y2[l],n-1);
szx[p]=szy[p]=3;
return;
}
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
build(ls,l,mid),build(rs,mid+1,r);
merge(x[ls],szx[ls],x[rs],szx[rs],x[p],szx[p]);
merge(y[ls],szy[ls],y[rs],szy[rs],y[p],szy[p]);
vec[p].resize(szx[p],szy[p]);
static int tranx[610],trany[610];
for(int i=0;i<szx[p];i++){
int &k=tranx[i];
for(k=0;k<szx[ls];k++)
if(std::max(x[ls][k].first,x[p][i].first)<=std::min(x[ls][k].second,x[p][i].second))
break;
}
for(int i=0;i<szy[p];i++){
int &k=trany[i];
for(k=0;k<szy[ls];k++)
if(std::max(y[ls][k].first,y[p][i].first)<=std::min(y[ls][k].second,y[p][i].second))
break;
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
++sons[vec[ls][tranx[i]][trany[j]]];
for(int i=0;i<szx[ls];i++)
for(int j=0;j<szy[ls];j++)
son[vec[ls][i][j]]=pl,pl+=sons[vec[ls][i][j]],sons[vec[ls][i][j]]=0;
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
son[vec[ls][tranx[i]][trany[j]]][sons[vec[ls][tranx[i]][trany[j]]]++]=vec[p][i][j];
for(int i=0,j=0,g=0,w=0;i<szx[p];i++){
tranx[i]=j;
g+=x[p][i].second-x[p][i].first+1;
if(w+(x[rs][j].second-x[rs][j].first+1)==g)w+=x[rs][j].second-x[rs][j].first+1,++j;
}
for(int i=0,j=0,g=0,w=0;i<szy[p];i++){
trany[i]=j;
g+=y[p][i].second-y[p][i].first+1;
if(w+(y[rs][j].second-y[rs][j].first+1)==g)w+=y[rs][j].second-y[rs][j].first+1,++j;
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
++sons[vec[rs][tranx[i]][trany[j]]];
for(int i=0;i<szx[rs];i++)
for(int j=0;j<szy[rs];j++)
son[vec[rs][i][j]]=pl,pl+=sons[vec[rs][i][j]],sons[vec[rs][i][j]]=0;
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
son[vec[rs][tranx[i]][trany[j]]][sons[vec[rs][tranx[i]][trany[j]]]++]=vec[p][i][j];
}
void dfs(int p,int l,int r,int book=1){
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
for(int *u=son[vec[p][i][j]],*ed=u+sons[vec[p][i][j]];u!=ed;++u)
tr[vec[p][i][j]].add_eq(tr[*u]);
if(l==r){
static constexpr int trans[]={0,2,1};
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
ans[l][i][j]=tr[vec[p][trans[i]][trans[j]]];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
op[l][trans[i]][trans[j]].apply(lz[vec[p][i][j]]);
}else{
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
dfs(ls,l,mid),dfs(rs,mid+1,r);
}
for(int i=0;i<szx[p];i++)
for(int j=0;j<szy[p];j++)
for(int *u=son[vec[p][i][j]],*ed=u+sons[vec[p][i][j]];u!=ed;++u){
if(book) lz[vec[p][i][j]].apply(lz[*u]);
lz[vec[p][i][j]].apply(tr[*u]);
}
}
void solve(int m){
pl=pool,dl=dool;
for(int i=n+1;i<=cnt;i++) tr[i].clr(),lz[i].clr();
cnt=n;
build(1,0,m-1);
static int tranx[100010],trany[100010];
for(int i=0;i<szx[1];i++) for(int j=x[1][i].first;j<=x[1][i].second;j++) tranx[j]=i;
for(int i=0;i<szy[1];i++) for(int j=y[1][i].first;j<=y[1][i].second;j++) trany[j]=i;
for(int i=0;i<n;i++) ++sons[vec[1][tranx[X[i]]][trany[Y[i]]]];
for(int i=0;i<szx[1];i++)
for(int j=0;j<szy[1];j++)
son[vec[1][i][j]]=pl,pl+=sons[vec[1][i][j]],sons[vec[1][i][j]]=0;
for(int i=0;i<n;i++) son[vec[1][tranx[X[i]]][trany[Y[i]]]][sons[vec[1][tranx[X[i]]][trany[Y[i]]]]++]=i;
dfs(1,0,m-1,0);
for(int i=0,p=0;i<szx[1];i++) for(int j=x[1][i].first;j<=x[1][i].second;j++) tranx[j]=p++;
for(int i=0,p=0;i<szy[1];i++) for(int j=y[1][i].first;j<=y[1][i].second;j++) trany[j]=p++;
for(int i=0;i<n;i++) X[i]=tranx[X[i]],Y[i]=trany[Y[i]];
}
void solve(const int n, const int m, const int p[], const Data d[],
const int x1[], const int x2[], const int y1[], const int y2[],
const Operation o[][3][3], Data ans[][3][3]) {
::n=n;
for(int i=0;i<n;i++) tr[i]=d[i],X[i]=i,Y[i]=p[i];
for(int l=0,r;l<m;l=r+1){
r=std::min(l+B,m-1);
for(int i=l;i<=r;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
op[i-l][j][k]=o[i][j][k];
for(int i=l;i<=r;i++) X1[i-l]=x1[i],Y1[i-l]=y1[i],X2[i-l]=x2[i],Y2[i-l]=y2[i];
solve(r-l+1);
for(int i=l;i<=r;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
ans[i][j][k]=::ans[i-l][j][k];
}
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 10ms
memory: 60776kb
input:
100000 21489 6 49113 7 60173 8 74888 6 57756 3 9404 3 13780 2 73818 5 6331 2 19759 5 90563 3 2784 10 69925 9 2212 7 57523 1 92604 9 95844 2 89870 2 33003 10 53846 3 79588 5 33137 6 75240 3 12376 4 92734 3 12176 3 64048 10 48444 1 28074 9 54930 9 97809 9 53147 7 51667 6 58543 1 84925 5 47057 4 29059 ...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 ee61544cfd5acacff8d11390f5f20426fcbe22adfe8a295dfe346f79fc3c257cfc8ae4d4ece3d730f9756e0ddf6230c9f2e560faf8c0399edcb813a1bc3f6d77e93929da9392b5d8ce04a032fc5b5723fc7351...
result:
ok ok
Test #2:
score: 10
Accepted
time: 20ms
memory: 63420kb
input:
100000 69665 10 15278 6 72674 3 93522 5 74471 9 49365 7 85608 8 3729 9 69243 5 39180 3 26876 7 51094 2 83441 10 24690 2 44686 1 32112 1 61821 10 6740 4 72546 7 86502 3 89364 3 83731 9 91821 5 33767 5 53574 4 87221 4 41642 1 29525 2 56500 7 37335 8 62608 5 3254 8 73587 10 42659 7 63576 8 14107 4 1534...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fd767c6bfcdb2c7afd9ed2e2f047d9f3fa87c787f1c9d65efd92c1c7fccb703afdda743ff49493cb91555eb3e98b2acefeee99a6ce42d0b7f0d3cd85ff7c129acae7e8b3f16eb33dc9cc80afb09767e5ada025...
result:
ok ok
Test #3:
score: 10
Accepted
time: 80ms
memory: 62900kb
input:
100000 78088 3 94024 5 14771 10 58942 3 40949 6 98101 9 33561 9 56898 1 71177 2 43263 10 50994 1 12034 4 10960 6 52881 8 85650 4 76415 9 89558 8 28725 1 72008 7 11199 7 93193 1 41847 1 87298 10 4736 2 38329 1 59361 3 23711 4 33455 3 19302 5 95242 5 72096 10 22776 10 22864 3 12030 4 10659 3 4369 4 50...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fadbc857fcbc5977fbe81bfbf93f0ccefc9890dafa1b1548f9facf4afc8d9738fae05631f6a59bd3f94a302df62bd276f3108b57fb820f8ff2e90b1f8d696dc4c8774093915daba0a2b9586fd56e9bbb935f66...
result:
ok ok
Test #4:
score: 10
Accepted
time: 145ms
memory: 63688kb
input:
100000 15457 6 14735 3 48523 9 17776 5 68591 2 8610 7 52792 2 91312 2 49712 4 89956 9 82574 3 73360 6 13459 5 53721 6 24488 7 61581 4 53165 3 70221 6 15429 4 54374 6 11515 3 29260 2 59020 1 83031 9 52325 8 66096 7 33608 3 37002 5 47053 4 18424 5 96629 9 90730 5 27347 4 86984 8 54072 9 60283 6 91967 ...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fa89c838f8dddd11ff5f68d5fa363728f87919f8ff016793f99b64b6ffe0ffc0fecabe0bf2fcc23aeef04eb5ed4649b8f04f08fcdbcbe077f2f17075ec23d9dbd500c016e608d919ce58212ed60f132bfcdefc...
result:
ok ok
Test #5:
score: 10
Accepted
time: 326ms
memory: 63324kb
input:
100000 10785 6 67618 7 71918 3 60330 3 77568 6 89055 6 97051 4 67553 6 47702 4 41964 7 94295 5 9078 10 83630 2 36139 7 1095 1 78642 10 19366 7 34967 7 63518 7 46007 6 71140 2 54894 6 19374 8 55751 2 31700 2 89914 7 30669 5 51687 9 92079 2 19715 3 62368 10 89803 4 94288 6 90020 4 24022 8 14984 5 7044...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fffe153efcd98bf4f51948a2f9bba43cfd3966b9f11d11bbfe193b1afc7cb09cf8b24055d3d85ce2e1cdb8f5ed5f4c22ece69c86f0fcba06f49c1bceee50b324f2cb8a0bf3a0e6989160ac7af046676af77044...
result:
ok ok
Test #6:
score: 10
Accepted
time: 666ms
memory: 62968kb
input:
100000 36768 6 3257 1 38397 5 72801 6 98082 10 63603 1 38820 1 37756 1 93147 5 75201 7 74160 7 20700 8 38068 2 16497 3 27739 10 171 2 72017 3 74213 10 14872 3 18805 2 84023 7 58120 9 93591 6 35081 9 76973 6 93826 9 70815 4 69999 9 67045 3 73707 2 97041 4 53284 1 55126 8 49168 2 42869 9 56612 7 9218 ...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 f90b8ca4f1151726fe7b7092fc075a11fc4e248bfc08bd33f8f9f905f0690bcefe5555f4f3141f33d04105c5f544bdbfc79f968798cd0d47e888bdeddd78611add3635acfac759b08e414947152fc2dcdce166...
result:
ok ok
Test #7:
score: 10
Accepted
time: 824ms
memory: 63212kb
input:
100000 19404 6 58021 10 99136 9 33294 9 82920 9 19772 1 39629 8 81111 3 18581 8 76268 2 45876 3 74784 2 56521 1 10286 10 13164 6 62333 9 17934 2 34029 6 62141 8 33500 3 7308 2 14932 7 28141 2 44757 7 66094 6 72585 7 72091 7 77173 10 45152 6 55439 9 19447 6 64886 7 93539 6 21564 3 49343 4 86077 5 777...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fc84c79bfc18032dfc4796d5ee8e33ddfc5d6fbef67107c5fa810a28fc00b900ffb99664dab7aaf9f2ebb693dab63edaf6d791e0ff62853bfbcce7c7c8432527eca27857d968eebaf707c43fef67b427df5b3b...
result:
ok ok
Test #8:
score: 10
Accepted
time: 1001ms
memory: 63112kb
input:
100000 72061 10 47496 4 19781 2 96174 10 93995 7 88807 9 46892 3 69085 9 27000 10 65702 3 94626 9 21066 2 92106 5 6473 10 80120 6 60915 7 75590 10 20507 9 59807 5 17324 3 8888 2 98609 10 54420 3 52885 10 22226 6 72252 9 1364 3 56566 10 91972 10 75258 1 73170 10 42425 9 31108 6 70811 10 79318 8 57104...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fa9fd8ddfbd8282af828eee6ffdf5ee3f8694abafe61ef00f80bebdff8ab111afeb95462b9c8ce17cdc0143ef8bae4fdc43b7c3dda17bf8cff7701b4cf7c3d9adb19375bffb9ba996e535dad86b27d0bf7d368...
result:
ok ok
Test #9:
score: 10
Accepted
time: 1161ms
memory: 66188kb
input:
100000 29532 6 63952 4 55998 9 34077 9 76926 7 56075 9 35680 5 46651 5 78718 8 29942 2 84998 4 61823 2 51347 6 92943 9 46990 6 81833 3 49223 4 18772 5 45966 6 8064 6 6480 5 95762 8 69632 2 23094 1 23768 7 79943 6 6105 3 59408 5 61416 1 47545 10 19592 2 29854 6 66637 1 14390 9 83087 7 55531 7 37485 3...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 fd12f9c4fb50b3b7fc486596fe126b37f31a7260fcb28957fdb3be24f7e71b61fc97d298fc22fd23fc5f8dbbfd3bd2e3e8275ab9ee95105cb51cbae1e056db9ee7fdabbf92803f60bde0a5dbb99b103ef9a672...
result:
ok ok
Test #10:
score: 10
Accepted
time: 1319ms
memory: 66144kb
input:
100000 84676 7 57603 9 20352 4 16697 1 90115 6 48507 9 75362 10 49332 5 47705 5 85561 5 68241 5 46443 5 9688 5 45710 4 51757 3 1477 2 48114 4 74948 5 61999 3 80177 1 40560 8 22763 8 2493 9 78031 1 80799 10 77825 3 3332 1 35593 4 9067 9 26247 2 93914 10 2881 5 82785 2 86644 7 9764 6 50005 6 11432 8 8...
output:
token978cac5bce575ae5a53c48a9c59b8a97fd0da24c7b5f8deb061a4473de6709058b9db2489d53adb3de995cabb61d741b3780add03bf8f97519e1c7444dd72ff1 f8cd14acfef5e15efc955b99fc312ba1fc057208fc1fe520ee46974ff7493c7afe00e43aa97ba887aa0e11f8af10bef4e8b34f43e8344ce4ef549cb8f682a2bff6b8af52f546ed3ba6c69d81fc49f0402e5abf...
result:
ok ok