QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311850 | #8139. Ayano and sequences | ship2077 | TL | 735ms | 82768kb | C++14 | 3.0kb | 2024-01-22 21:22:06 | 2024-01-22 21:22:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
typedef unsigned long long ull;
constexpr int M=5e5+5;
vector<array<int,3>>upd[M];
vector<array<int,4>>qry[M];
int n,m,op,l,r,z;ull ans[M];
struct odt{
int l,r,col,tim;
bool operator <(const odt &a) const
{return l<a.l;}
}; set<odt>s;
struct matrix{
ull mat[3][3];
void clear(){memset(mat,0,sizeof(mat));}
void init(){clear();mat[0][0]=mat[1][1]=mat[2][2]=1;}
matrix operator *(matrix a){
matrix ans;ans.clear();
for (int k=0;k<3;k++)
for (int i=0;i<3;i++) if (mat[i][k])
for (int j=0;j<3;j++) if (a.mat[k][j])
ans.mat[i][j]+=mat[i][k]*a.mat[k][j];
return ans;
}
}V,C;
struct segtree{matrix ans,lazy;}tr[M<<2];
void addtag(int x,matrix z){
tr[x].ans=tr[x].ans*z;
tr[x].lazy=tr[x].lazy*z;
}
void pushdown(int x){
addtag(ls(x),tr[x].lazy);
addtag(rs(x),tr[x].lazy);
tr[x].lazy.init();
}
void pushup(int x){
tr[x].ans.mat[0][0]=tr[ls(x)].ans.mat[0][0]+tr[rs(x)].ans.mat[0][0];
tr[x].ans.mat[0][1]=tr[ls(x)].ans.mat[0][1]+tr[rs(x)].ans.mat[0][1];
tr[x].ans.mat[0][2]=tr[ls(x)].ans.mat[0][2]+tr[rs(x)].ans.mat[0][2];
}
void build(int l,int r,int x){
tr[x].ans.mat[0][0]=r-l+1; tr[x].lazy.init();if (l==r) return ;
int mid=l+r>>1;build(l,mid,ls(x));build(mid+1,r,rs(x));
}
void modify(int L,int R,matrix z,int l=1,int r=n,int x=1){
if (L<=l&&r<=R) return addtag(x,z),void();
int mid=l+r>>1;pushdown(x);
if (L<=mid) modify(L,R,z,l,mid,ls(x));
if (R>mid) modify(L,R,z,mid+1,r,rs(x));
pushup(x);
}
ull query(int L,int R,int l=1,int r=n,int x=1){
if (L<=l&&r<=R) return tr[x].ans.mat[0][2];
int mid=l+r>>1;ull ans=0;pushdown(x);
if (L<=mid) ans+=query(L,R,l,mid,ls(x));
if (R>mid) ans+=query(L,R,mid+1,r,rs(x));
return ans;
}
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
auto split(int x){
auto it=s.lower_bound({x,0,0,0});
if (it!=s.end()&&(*it).l==x) return it;
odt tmp=*--it;s.erase(it);
s.insert({tmp.l,x-1,tmp.col,tmp.tim});
return s.insert({x,tmp.r,tmp.col,tmp.tim}).first;
}
void modify1(int l,int r,int z,int tim){
auto R=split(r+1),L=split(l);
for (auto it=L;it!=R;it++){
qry[(*it).tim-1].push_back({(*it).l,(*it).r,(*it).col,-1});
qry[tim-1].push_back({(*it).l,(*it).r,(*it).col,1});
} s.erase(L,R); s.insert({l,r,z,tim});
}
void modify2(int l,int r,int z,int tim){upd[tim].push_back({l,r,z});}
int main(){
n=read();m=read();
for (int i=1;i<=n;i++) s.insert({i,i,read(),1});
for (int i=1;i<=m;i++){
op=read();l=read();r=read();z=read();
if (op==1) modify1(l,r,z,i);
if (op==2) modify2(l,r,z,i);
}
modify1(1,n,0,m+1);build(1,n,1);
V.mat[0][0]=V.mat[1][1]=V.mat[2][2]=1;
C.mat[0][0]=C.mat[1][1]=C.mat[1][2]=C.mat[2][2]=1;
for (int i=1;i<=m;i++){
for (auto [l,r,z]:upd[i]) V.mat[0][1]=z,modify(l,r,V);
addtag(1,C);
for (auto [l,r,id,coef]:qry[i])
ans[id]+=query(l,r)*coef;
}
for (int i=1;i<=n;i++) printf("%llu ",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 28872kb
input:
5 6 1 2 3 4 5 2 2 4 1 1 2 3 3 2 3 4 3 1 3 5 4 2 1 5 2 1 1 3 2
output:
2 12 12 36 0
result:
ok single line: '2 12 12 36 0 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 28100kb
input:
10 10 9 2 8 8 6 5 4 8 5 3 2 2 6 268792718 2 7 8 125908043 2 2 3 150414369 2 6 10 856168102 2 4 5 274667941 1 1 9 6 2 2 6 646837311 2 6 6 105650419 2 7 9 254786900 2 1 7 73936815
output:
0 1795206697 5993176714 2215968376 4768635998 46271691633 0 5629806604 0 0
result:
ok single line: '0 1795206697 5993176714 221596...8 46271691633 0 5629806604 0 0 '
Test #3:
score: 0
Accepted
time: 0ms
memory: 28048kb
input:
100 100 59 96 34 48 8 72 67 90 15 85 7 90 97 47 25 44 69 6 86 32 57 47 21 9 63 10 75 35 61 11 75 100 50 53 15 40 35 86 97 77 27 30 35 91 72 87 56 25 95 70 60 22 47 49 68 61 35 87 16 54 20 91 35 39 64 21 58 44 5 20 61 87 66 74 45 64 9 84 1 26 32 63 53 33 96 47 73 94 45 32 99 14 44 48 1 78 7 10 68 52 ...
output:
274832111654 0 0 0 309880184 347085980 0 5208679581 0 0 1391288895991 462582810805 0 309880184 0 309880184 0 2202105800064 0 1470341419 1160461235 0 0 2697359985855 1041257940 46672170424 0 951255722094 0 0 1329201652617 121425405126 683986398348 138178909497 1470341419 0 0 2492776390926 80323798299...
result:
ok single line: '274832111654 0 0 0 309880184 3...94 609693254112 307568016399 0 '
Test #4:
score: 0
Accepted
time: 49ms
memory: 30592kb
input:
5000 5000 987 4237 3891 429 4358 1145 851 4174 4670 3571 3747 3238 391 3689 2144 3561 3383 56 1508 777 4705 733 4730 2292 2524 3519 1996 588 3682 2682 1493 270 4145 885 3015 644 2669 4757 439 387 4020 3944 1420 1750 1968 4067 2771 1865 809 2941 1286 1478 1433 3465 2064 1100 1926 2912 3971 1266 3923 ...
output:
1264113586735714 112938905619174 3426351370 0 3616678527569466 12410599127 20863739455 1943199759422496 6860659882 24097078636 4940352344 3066105550 4940352344 8984247757 0 0 1873308016 690360017267298 1463634140028344 34786416053526 10565974962 491847076791519 0 3066105550 337181826086845 954432374...
result:
ok single line: '1264113586735714 1129389056191...2 17437388085 2534760806780036 '
Test #5:
score: 0
Accepted
time: 735ms
memory: 79848kb
input:
100000 100000 9411 13081 2149 19907 93611 24114 59730 5867 96529 35050 21890 2981 87777 82418 96659 18374 76106 7614 79526 45826 56158 33510 42240 53971 75573 98727 13513 35449 65290 67552 80720 51348 94140 32021 97828 38348 52399 51728 27676 75498 22825 15163 89905 26204 15157 2855 99583 81109 1142...
output:
2860862817585182004 0 0 668421922369962250 0 4558260292 170686179720145772 270419400917769555 823080596 30396324352 991325503472415378 549309244400642225 1470105139512235415 0 1216640397961225546 21449668079 0 0 5381340888 197095337844692543 11450152672832485 823080596 345580727782852526 21449668079...
result:
ok single line: '2860862817585182004 0 0 668421...141382845 0 920528238127173667 '
Test #6:
score: 0
Accepted
time: 677ms
memory: 82060kb
input:
100000 100000 25539 29221 6895 82089 18673 2890 99009 89855 30685 39232 82330 30021 87868 84659 66982 66291 48020 79364 42952 42770 19906 81288 92853 52547 89430 17447 7734 93014 55411 67422 67242 28915 3728 75454 99937 32948 87129 81803 14914 8713 63118 33277 88390 60658 49154 63938 46394 72649 204...
output:
3711628643750554324 556362386091535043 0 8028405448 8028405448 219909499354732110 0 1323849903041530801 14525054661 29347414077490544 980768499542767970 0 234259419233115560 8028405448 0 0 13435740174125371 8028405448 0 1268120972702792862 85232791231015303 8028405448 7591907024531183667 0 0 6227380...
result:
ok single line: '3711628643750554324 5563623860...31283976 27233070503118890 0 0 '
Test #7:
score: 0
Accepted
time: 674ms
memory: 78824kb
input:
100000 100000 76259 10770 87448 3054 67926 81667 95184 41139 64840 76118 18577 22469 96470 78388 28793 14208 95743 59626 40970 7011 7847 4874 362 94226 68695 27655 1955 9363 69723 34588 10660 47697 13315 51590 34750 3356 21858 79173 2151 98823 46514 51392 54171 52009 7343 81918 93206 64189 35767 190...
output:
1296206533755864325 3408617157162819 1367176386 292548752396599025 0 0 1367176386 14288338007 2734352772 1051580445916368582 3071278704 4068600777268612311 618819063961521440 4675194818878852042 362754832564412528 5790497232 307885871989844920 455725462 0 5790497232 0 931292207145677471 0 1066559415...
result:
ok single line: '1296206533755864325 3408617157...0759545046 5915105370229767921 '
Test #8:
score: 0
Accepted
time: 723ms
memory: 80628kb
input:
100000 100000 92387 35422 24898 32532 92988 84636 99872 57831 31700 47597 79017 25316 96560 4822 31820 62125 8873 31377 38988 12468 71596 52652 40575 1313 82552 37864 96176 34224 84035 10267 29886 57968 31414 95022 61051 97957 89292 9248 89389 23526 19511 12610 95760 86463 65531 43001 40017 88433 26...
output:
171366078874572813 20509648584758088 2437426492745132371 0 960915322 0 960915322 1921830644 156529249442565108 0 0 577750733721075019 78581487497386145 27517495958 2719915459771023390 0 960915322 1960237471028313164 0 4545736696214496575 0 336463929447759705 3843661288 1921830644 22760558906 9609153...
result:
ok single line: '171366078874572813 20509648584...3904163920 1374231424175143263 '
Test #9:
score: 0
Accepted
time: 726ms
memory: 82768kb
input:
100000 100000 8515 51563 5451 94713 9537 30709 63343 41819 65855 51779 39457 85060 96650 74359 93631 10042 80788 11639 69710 76709 68048 33133 23893 75696 96409 23880 14590 91789 74156 10137 49112 35534 41001 71159 63159 35661 91318 39323 76627 89445 35612 30725 94245 20918 99528 36789 86829 79973 8...
output:
54191958 0 343919527782549352 9031993 0 842744505716284651 10535466989 4520361277 0 18063986 1281928441250648448 3876431406219851657 33832389186580283 203761488938235284 246691638186991544 0 2299774162079501436 0 36561691059466635 0 0 124203447330148627 273331593346351168 480610589593712254 18063986...
result:
ok single line: '54191958 0 343919527782549352 ...49109467 0 2983109225563613099 '
Test #10:
score: 0
Accepted
time: 689ms
memory: 79276kb
input:
100000 100000 91939 407 10197 24191 58791 9486 68030 25807 11 88665 32600 12100 29445 33496 96658 57959 28510 83389 67729 40950 55989 80911 31402 17375 42970 99496 8811 8138 88468 10007 92530 21612 83292 81887 97972 62965 58752 36694 96568 46851 75905 91943 60026 88076 57717 97872 936 71513 74917 52...
output:
1878499310067731347 0 0 157334864681509345 0 594964574666066187 0 5582057088 199633267174389376 0 6083714190617 2574062040646687147 148402260162 0 171103271643568965 91941775271241949 30136542084 731547080385 259559763726095800 9101796151 0 1274850907901014267 7699837152 15187121185 5308948889437840...
result:
ok single line: '1878499310067731347 0 0 157334...7203933 0 609748350226766294 0 '
Test #11:
score: -100
Time Limit Exceeded
input:
500000 500000 30518 196518 274071 359971 50121 204862 343967 173607 119138 190754 219513 171337 183499 49873 42337 161387 397647 495917 413076 418417 368000 422012 195703 305826 26356 334728 35984 133227 226371 132864 493387 111196 258251 76565 244054 213672 267148 179390 200005 67050 46349 2772 499...