QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361174 | #8229. 栈 | XY_Eleven | 40 | 213ms | 32756kb | C++23 | 6.1kb | 2024-03-22 21:15:27 | 2024-03-22 21:15:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outint2_(e,e1,e2) printf("%d%c",e," \n"[(e1)==(e2)])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define outll2_(e,e1,e2) printf("%lld%c",e," \n"[(e1)==(e2)])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) (1ll*(e))
#define pb push_back
#define ft first
#define sc second
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())
#define debug(x) printf("%s=%d\n",#x,x)
#define x0 _x0_
#define y1 _y1_
#define ffo fflush(stdout)
cLL mod=998244353,G=404;
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; }
template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
template <typename Type> Type gcd(Type X_,Type Y_) { Type R_=X_%Y_; while(R_) { X_=Y_; Y_=R_; R_=X_%Y_; } return Y_; }
template <typename Type> Type lcm(Type X_,Type Y_) { return (X_/gcd(X_,Y_)*Y_); }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<0) w1+=w2; return w1; }
template <typename Type> Type md_(Type w1,const Type w2=mod) { w1%=w2; if(w1<=0) w1+=w2; return w1; }
void ex_gcd(LL &X_,LL &Y_,LL A_,LL B_)
{ if(!B_) { X_=1ll; Y_=0ll; return ; } ex_gcd(Y_,X_,B_,A_%B_); X_=md(X_,B_); Y_=(1ll-X_*A_)/B_; }
LL inv(LL A_,LL B_=mod) { LL X_=0ll,Y_=0ll; ex_gcd(X_,Y_,A_,B_); return X_; }
template <typename Type> void add(Type &w1,const Type w2,const Type M_=mod) { w1=md(w1+w2,M_); }
void mul(LL &w1,cLL w2,cLL M_=mod) { w1=md(w1*md(w2,M_),M_); }
template <typename Type> Type pw(Type X_,Type Y_,Type M_=mod) { Type S_=1; while(Y_) { if(Y_&1) mul(S_,X_,M_); Y_>>=1; mul(X_,X_,M_); } return S_; }
mt19937 gen(time(NULL)); int rd() { return abs((int)gen()); }
cint N=1.02e5;
int n,Q;
vector <pair<int,pair<LL,LL> > > q[N];
vector <int> v[N];
array <LL,2> a[N];
struct Node
{
int l,r,mid;
LL ls,rs,sum,sum2,lcnt;
}t[N<<2|1];
void bld(int p,int l,int r)
{
int mid=l+r>>1;
t[p]={l,r,mid,0ll,0ll,0ll,0ll,0ll};
ret(l>=r);
bld(p<<1,l,mid),bld(p<<1|1,mid+1,r);
}
LL ans[N];
bool vis[N],b[N];
int K;
void setf(int p,int k)
{
if(vis[k])
t[p].ls=t[p].rs=t[p].sum=0ll;
else
{
if(b[k]) t[p].rs=a[k][0],t[p].sum=a[k][0]*a[k][1];
else t[p].ls=a[k][0];
}
vis[k]=!vis[k];
}
LL work(int p,LL c)
{
// printf("work [%d,%d]:%lld,%lld\n",t[p].l,t[p].r,t[p].lcnt,c);
if(t[p].l>=t[p].r) return c*a[t[p].l][1];
if(c<=t[p].lcnt) return work(p<<1,c);
else return (work(p<<1|1,c-t[p].lcnt)+t[p].sum2);
}
pair <array <LL,2>,LL> sum(int p1,int p2)
{
if(t[p2].ls>=t[p1].rs) return {{t[p1].ls+(t[p2].ls-t[p1].rs),t[p2].rs},t[p2].sum};
return {{t[p1].ls,t[p2].rs+(t[p1].rs-t[p2].ls)},t[p2].sum+work(p1,t[p1].rs-t[p2].ls)};
}
void pup(int p)
{
t[p].sum2=work(p<<1,t[p].lcnt=max(t[p<<1].rs-t[p<<1|1].ls,0ll));
auto w=sum(p<<1,p<<1|1);
t[p].ls=w.ft[0],t[p].rs=w.ft[1],t[p].sum=w.sc;
}
void change(int p)
{
if(t[p].l>=t[p].r)
{
setf(p,K);
return ;
}
change(p<<1|(K>t[p].mid));
pup(p);
}
void Change(int k)
{
K=k;
change(1);
}
int L,R;
vector <int> g;
void qry(int p)
{
if(L<=t[p].l&&t[p].r<=R)
{
g.pb(p);
return ;
}
if(L<=t[p].mid) qry(p<<1);
if(R>t[p].mid) qry(p<<1|1);
}
stack <pair<int,LL> > st;
LL Qry(int k,LL c)
{
// printf("\nquery %d,%lld\n",k,c);
L=1,R=k,g.clear();
qry(1);
clean(st);
LL sum=0ll;
for(auto i:g)
{
LL w=t[i].ls;
while(!st.empty()&&w>=st.top().sc)
w-=st.top().sc,st.pop();
if(!st.empty()) st.top().sc-=w;
st.push({i,t[i].rs});
}
while(!st.empty())
{
int p=st.top().ft; LL c2=st.top().sc;
get_min(c2,c); c-=c2;
st.pop();
// printf("[%d,%d]:%lld(%lld)\n",t[p].l,t[p].r,c2,t[p].rs);
sum+=work(p,c2);
}
return sum;
}
void print(int p)
{
// printf("print %d:[%d,%d] %lld(%lld)&%lld\n",p,t[p].l,t[p].r,t[p].ls,t[p].lcnt,t[p].rs);
ret(t[p].l>=t[p].r);
print(p<<1),print(p<<1|1);
}
void main_solve()
{
inpr(n,Q);
int opt;
For(i,1,Q)
{
inint(opt);
if(opt==3)
{
int k; LL l,r;
scanf("%d%lld%lld",&k,&l,&r);
q[k].pb({i,{l,r}});
}
else
{
int l,r; inpr(l,r);
v[l].pb(i),v[r+1].pb(i);
if(opt==1)
{
LL c,w; scanf("%lld%lld",&c,&w);
a[i]={c,w};
}
else
{
LL c; scanf("%lld",&c);
a[i]={c,0ll};
}
b[i]=(opt==1);
}
}
bld(1,1,Q);
memset(ans,0xff,(Q+1)*sizeof(LL));
For(i,1,n)
{
// printf("\ni=%d\n",i);
for(auto j:v[i]) Change(j);
for(auto [id,c]:q[i])
ans[id]=Qry(id,c.sc)-Qry(id,c.ft-1ll);
// printf("\n"); print(1);
}
For(i,1,Q) if(ans[i]!=-1ll)
outll(ans[i]);
}
int main()
{
// ios::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
// rsand(time(NULL));
// main_init();
// int _; inint(_); For(__,1,_) // T>1 ?
// printf("\n------------\n\n"),
main_solve();
return 0;
}
/*
2 2 2 1 1
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 9392kb
input:
4907 4910 2 763 3330 1 3 307 1 1 1 2262 3430 22699 89397 1 1915 4000 51541 67587 2 212 2990 9763 2 1086 2162 1 2 1813 4496 16760 1 51 2796 68005 99390 1 1267 1519 74236 66178 3 1768 23808 54314 2 900 4122 27758 3 3287 17350 28989 2 3277 4024 3633 2 444 4866 1 2 353 4219 1061 1 987 3141 99906 17320 2...
output:
0 3032090730 903396180 471569175 200648623 98486697 214102593 123945 113900940 61782451 0 0 0 762429740 321140700 661791594 97825657 5854255411 0 1747798348 6502828468 2351056740 122249391 283261500 5250788038 1145132507 140071334 0 118545795 4845967480 8355899456 84280112 128431809 4992966775 98734...
result:
wrong answer 7th numbers differ - expected: '647114751', found: '214102593'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 206ms
memory: 30892kb
input:
99999 99998 1 5026 18575 27178 90423 3 30623 1 1 3 76936 1 1 1 77021 95683 84664 24734 1 46085 74886 40512 11266 3 5048 8594 22468 1 53318 77721 97151 70784 1 70645 91192 37556 13013 1 56752 56940 91812 62887 1 7928 34576 87339 69404 3 74875 32807 100970 3 22338 17221 25771 3 21421 20602 57957 3 717...
output:
0 0 1254619125 2139315110 593473604 2592655824 3657975552 5652513833 110091352 1226646296 1989326852 238600374 6208421260 1133345895 925424768 14415119878 2900664601 15486317750 28487172978 4722824224 16341882407 899316516 38935050954 988382364 13466737951 9077631207 2449683584 5875277101 7875260146...
result:
wrong answer 4th numbers differ - expected: '4366274868', found: '2139315110'
Subtask #3:
score: 16
Accepted
Test #12:
score: 16
Accepted
time: 131ms
memory: 30776kb
input:
100000 99993 1 47773 70467 16065 1 2 52349 78446 2304 3 40821 1 1 1 40216 93069 78144 1 1 41089 43671 76025 1 2 35263 68629 31066 3 79881 13534 57327 3 5556 1 1 2 21962 38192 1 1 664 58116 9417 1 3 28089 6039 7989 2 88500 90302 9946 3 63215 49410 60770 2 11069 89527 57581 2 70303 97603 12363 1 3420 ...
output:
0 43794 0 1951 11361 129 898 29245 7969 1947 34972 16405 59952 123666 24537 68209 34537 0 32225 37527 0 31810 16824 96178 14285 300941 57614 1602 129470 61935 4068 114182 17609 152949 26099 179359 250368 4796 183349 125791 17414 61871 42058 0 2698 183297 23029 54464 0 26259 204595 35604 0 0 18437 29...
result:
ok 33281 numbers
Test #13:
score: 0
Accepted
time: 126ms
memory: 30812kb
input:
100000 99999 3 11279 1 1 1 21196 82827 47041 1 2 58608 97529 1 2 22065 32528 37154 1 2138 16260 96858 1 1 25755 42875 82334 1 1 31799 48594 28327 1 3 58271 16371 33060 1 9407 50398 53680 1 2 40505 54132 176725 2 4626 22919 41250 2 28476 63110 133245 2 501 87564 1 2 5927 27401 96494 2 27254 64078 1 2...
output:
0 16690 27551 1442 4671 0 35160 4953 1559 3430 1768 0 0 11628 0 0 2495 13673 0 0 162093 135864 330 17312 0 29074 0 0 0 33641 51926 7051 0 0 42277 0 44110 543 12418 51322 9338 89794 9387 44052 43969 170272 42203 209676 5275 15969 11537 29757 26609 8288 33600 0 21384 48804 75598 11624 67508 10170 1751...
result:
ok 33467 numbers
Test #14:
score: 0
Accepted
time: 164ms
memory: 30780kb
input:
99993 99998 3 67041 1 1 3 6929 1 1 2 17524 32038 1 2 61604 73005 1 3 89616 1 1 2 40031 62338 1 3 58255 1 1 1 13009 67563 20939 1 1 73959 97229 47418 1 2 60834 61638 3740 2 29078 66369 1909 3 20355 4984 7284 2 75885 86625 3998 1 58692 90189 3242 1 3 99600 1 1 1 4102 8018 16478 1 3 53676 3918 8517 3 6...
output:
0 0 0 0 2301 0 4600 1472 56471 13213 0 143912 24988 0 59240 0 0 65385 5137 154745 70944 42704 209563 9676 121308 24627 52979 49278 37462 16444 0 1611 409040 392695 111628 265718 65783 55560 11142 45479 32621 118811 0 27594 239805 284844 19955 220309 8044 161759 1982 53200 41530 102413 43466 28624 17...
result:
ok 33389 numbers
Test #15:
score: 0
Accepted
time: 163ms
memory: 30724kb
input:
99991 99996 1 47657 83825 20467 1 2 18475 94316 1 1 45137 56194 42134 1 2 62287 64784 3656 1 34371 82222 66403 1 2 26982 76957 4461 2 1186 62584 1 2 63744 85641 5313 1 20658 59024 63800 1 2 51424 82606 5804 2 90768 91321 1 3 15951 1 1 2 51955 91548 1298 3 37870 8860 39509 3 8317 1 1 3 308 1 1 1 1977...
output:
0 30650 0 0 0 0 0 52497 2540 51822 0 22469 45077 10570 146261 11438 80060 21311 114935 197491 113332 156089 207620 36833 104730 21761 58044 72459 72699 105703 297859 98381 351013 75662 42544 50509 161825 375089 22703 209315 121760 4317 496943 121741 116864 11213 87742 871 452690 54302 100601 39830 2...
result:
ok 33262 numbers
Test #16:
score: 0
Accepted
time: 198ms
memory: 30724kb
input:
99997 99999 2 53252 91242 1 1 57337 88934 37260 1 1 16834 34642 93492 1 2 81166 94101 6093 1 46770 56947 41803 1 2 70882 88729 2179 2 55489 59818 1 1 29212 60579 61103 1 3 37904 1447 28743 1 68609 95313 51191 1 1 41758 51157 38733 1 3 57276 44404 49850 1 53448 66120 27464 1 1 64716 86889 8186 1 1 30...
output:
27297 5447 87454 7764 0 36668 9059 202784 226798 35791 44217 20176 425699 841344 314555 628121 279373 862035 1237442 638303 225509 1013325 143603 280017 469785 168019 102756 1008786 266597 5507 31097 1524290 288879 523157 706592 434088 1052960 282317 254606 633715 493060 281268 273353 139218 259977 ...
result:
ok 16863 numbers
Subtask #4:
score: 24
Accepted
Test #17:
score: 24
Accepted
time: 148ms
memory: 31032kb
input:
99999 99996 3 77889 1 10000000000 1 6316 86327 89644 386 3 9260 1 10000000000 2 2603 47234 69717 2 20260 73011 19290 2 62477 81233 26127 1 50140 68508 37004 98794 2 14449 22788 16063 1 43860 84932 50375 21777 1 67345 94584 28202 66610 2 661 68654 1 1 14411 94422 82738 61196 1 16563 94416 4920 38408 ...
output:
0 34602584 0 0 27739639583 1363823412 0 1902514434 1902514434 2147553884 1902514434 15794375094 0 4192446657 15797478185 13141921145 0 6351944090 5775183021 363222594 1995572111 2193350882 0 6843261316 5508935691 250667843 0 14181223499 7734049978 21958753162 12852564544 4496343819 15011219087 11331...
result:
ok 33196 numbers
Test #18:
score: 0
Accepted
time: 142ms
memory: 32756kb
input:
99993 100000 3 61460 1 10000000000 1 24890 92871 3803 26680 1 13860 37123 61687 5252 1 8370 24754 70468 14033 3 89253 1 10000000000 3 19857 1 10000000000 1 46250 80211 68621 64496 2 51133 69614 60852 1 6552 42728 61410 66775 3 16111 1 10000000000 3 48406 1 10000000000 2 46319 62460 3834 3 11455 1 10...
output:
0 101464040 1312857568 5413510318 4527244056 5089530194 4526096914 0 4475006240 7393292878 6354306906 5962661320 1073478334 14785061024 124598326 5273378126 3143834350 5315386486 567431731 3354264361 0 8452414800 16197376342 15594421332 7644906667 10259594309 15786872317 21575834611 25614641754 0 56...
result:
ok 33334 numbers
Test #19:
score: 0
Accepted
time: 162ms
memory: 30744kb
input:
99998 99996 3 40534 1 10000000000 1 89230 99016 8691 49307 1 73075 80610 27269 1760 1 80632 96125 13027 41376 1 55057 71990 82693 44377 2 11566 27301 1 2 23704 47061 1 1 67323 97867 14275 31136 1 11736 72566 78826 36301 3 70013 1 10000000000 1 23701 76122 6240 56626 2 71627 75885 1100 3 852 1 100000...
output:
0 6975596287 0 0 2144844585 6718561947 6718561947 2158130751 2917409114 3686398232 3317159253 1336852308 8373494196 2102154609 2709470190 1740124736 7659185913 1508488055 4242893725 8408091078 11875396012 18171183033 0 14595335642 18243076995 18521970659 18538979218 18538979218 20876408549 136521304...
result:
ok 33368 numbers
Test #20:
score: 0
Accepted
time: 170ms
memory: 30692kb
input:
99995 99996 3 45022 1 10000000000 2 3423 75909 1 1 54871 80611 9913 46243 2 12223 64484 1 1 12991 92385 39637 71608 3 20817 1 10000000000 3 14810 1 10000000000 3 85611 1 10000000000 3 34957 1 10000000000 3 22540 1 10000000000 2 11680 85376 4565 2 37283 97824 2191 3 84953 1 10000000000 3 56562 1 1000...
output:
0 2838326296 2838326296 2838326296 2838326296 2838326296 2354542648 2812903264 2631018944 2518569019 2681433168 2439582449 0 2681433168 2596475577 2439582449 0 7076261394 4449272647 15245942497 17667326760 15245942497 17667326760 17015058013 16860972874 42913399354 6034264601 96968820 12777724000 15...
result:
ok 33362 numbers
Test #21:
score: 0
Accepted
time: 213ms
memory: 32488kb
input:
99997 99996 3 68591 1 10000000000 2 11039 97222 1 1 34581 58556 66216 49214 1 42922 79247 32694 462 2 53032 58124 10301 3 34753 1 10000000000 1 22670 52566 70087 14019 3 55338 1 10000000000 3 30269 1 10000000000 1 4720 84384 20451 10356 3 11823 1 10000000000 1 37895 41892 96036 45498 2 19158 57043 7...
output:
0 3258754224 3269099790 982549653 211790556 1278106321 13591686831 9174283336 13929158983 10709860696 11476736634 24202776273 22066287959 23834159039 19695058244 28492871831 46736921586 859941225 5996946536 32463961710 31748786358 726580728 43724564767 39567498070 43724564767 57942980296 41944974287...
result:
ok 16689 numbers
Subtask #5:
score: 0
Skipped
Dependency #1:
0%