QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405113 | #8229. 栈 | dingdingtang11514# | 34 | 131ms | 49664kb | C++14 | 3.2kb | 2024-05-05 11:28:58 | 2024-05-05 11:29:00 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it])
#define In __inline
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
// mt19937_64 wql(514);
In int read() {
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
} const int N=1e5+100;
int n,m;
namespace S0 {
struct stk {
int sts[5005],stv[5005],tot;
void push(int val,int sum) {sts[++tot]=sum,stv[tot]=val;}
void pp(int cnt) {
while(tot && sts[tot]<=cnt) cnt-=sts[tot--];
if(tot) sts[tot]-=cnt;
} In int get(int p) {
int ret=0,i=1; while(i<=tot && p>=sts[i]) {
p-=sts[i];ret+=sts[i]*stv[i];i++;
} if(i<=tot) ret+=stv[i]*p;
return ret;
} In int get(int l,int r){
return get(r)-get(l-1);
} void print() {
For(i,1,tot) printf("%lld ",sts[i]);
puts("");
}
} mp[5005];
void solve0() {
while(m--) {
// printf("%d :\n",m);
int opt=read(); if(opt==1) {
int l=read(),r=read(),x=read(),y=read();
For(i,l,r) mp[i].push(y,x);
} else if(opt==2) {
int l=read(),r=read(),x=read();
For(i,l,r) mp[i].pp(x);
} else {
int x=read(),l=read(),r=read();
printf("%lld\n",mp[x].get(l,r));
} //For(i,1,n) mp[i].print();
// puts("");
}
}
} namespace S1 {
struct node{
int x=0,y=0; /// a_i = max ( x , a_i + y )
} tr[N<<2];
void pushtag(int u,int x,int y) {
tr[u].x+=x,tr[u].y=max(tr[u].y+x,y);
}
void pushdown(int u) {
int X=tr[u].x,Y=tr[u].y;
pushtag(u<<1,X,Y);pushtag(u<<1|1,X,Y);
tr[u].x=tr[u].y=0;
}
void mdf(int ql,int qr,int val,int u=1,int l=1,int r=n) {
if(ql<=l && r<=qr) pushtag(u,val,0);
else { int mid=(l+r)>>1; pushdown(u);
if(ql<=mid) mdf(ql,qr,val,u<<1,l,mid);
if(mid<qr) mdf(ql,qr,val,u<<1|1,mid+1,r);
}
} int ask(int pos,int u=1,int l=1,int r=n) {
if(l==r) return max(0+tr[u].x,tr[u].y);
int mid=(l+r)>>1; pushdown(u);
if(pos<=mid) return ask(pos,u<<1,l,mid);
return ask(pos,u<<1|1,mid+1,r);
}
void solve1() {
while(m--) {
// printf("%d :\n",m);
int opt=read(); if(opt==1) {
int l=read(),r=read(),x=read(),y=read();
mdf(l,r,x);
} else if(opt==2) {
int l=read(),r=read(),x=read();
mdf(l,r,-x);
} else {
int x=read(),l=read(),r=read();
int siz=ask(x);
printf("%lld\n",min(siz,r)-min(siz,l-1));
} //For(i,1,n) printf("%lld ",ask(i));
// puts("");
}
}
}
signed main() {
n=read(),m=read();
if(n<=5000 && m<=5000) S0::solve0();
else S1::solve1();
// S1::solve1();
return 0;
}
}signed main() {
// freopen("homework.in","r",stdin);
// freopen("homework.out","w",stdout);
return Mine::main();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 74ms
memory: 46248kb
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 647114751 123945 50793012 61782451 0 0 0 762429740 321140700 871619914 536311874 5361094892 0 1792521566 6640518748 2415375780 249435711 225987900 5250788038 1145132507 140071334 0 118545795 3086405469 5646099271 84280112 1232466642 4992966775 7968...
result:
ok 1622 numbers
Test #2:
score: 18
Accepted
time: 89ms
memory: 45164kb
input:
4992 4958 2 2965 3892 1 3 2141 1 1 3 4963 1 1 3 2298 1 1 3 2236 1 1 1 3393 4668 65533 8224 1 884 2343 86158 41289 3 4617 12174 63763 2 898 4236 44143 2 2860 4246 1 2 2696 3014 1 2 496 1635 15779 3 2230 8262 39805 2 3287 3627 5350 2 3443 4900 19874 1 535 1622 26926 88406 1 3272 3747 94290 19081 2 812...
output:
0 0 0 0 424276160 1302420216 0 393525459 0 188112684 0 38587680 696225296 717180100 2193537294 297696966 0 0 0 124461621 26876032 1609925499 0 3681040200 51602516 1502016 0 8636592 1138256753 196684293 0 16126264 959145423 58640451 1945754097 2949696960 0 3577791360 2029416288 2361290004 5882833609 ...
result:
ok 1597 numbers
Test #3:
score: 18
Accepted
time: 89ms
memory: 46076kb
input:
4980 4984 1 183 4891 75896 45281 2 767 3528 1367 3 2313 45535 49112 2 529 4006 1568 2 2114 2971 3819 3 3237 30655 31381 1 2074 2176 51631 35339 3 1602 95 16082 2 1340 3727 9249 2 105 1907 11928 3 2461 15189 33999 2 1450 1956 4721 1 700 4760 3043 92859 2 329 2992 6515 3 1295 10832 40486 2 3477 4447 8...
output:
162015418 32919287 723952628 851780891 1342808055 38307726 4701651115 903944603 240532672 652952020 1168430924 2253203546 3542990917 5872603595 305017015 657095398 25321688 1834305604 0 256832266 2732654054 1757936801 1158797383 656866283 3470700279 694675745 1042863834 76284096 6705704850 475899629...
result:
ok 1645 numbers
Test #4:
score: 18
Accepted
time: 87ms
memory: 46160kb
input:
4976 4948 2 858 1218 1 1 780 1528 70910 12344 1 681 4398 25997 59182 1 4564 4692 72420 96925 1 1124 2604 98159 98651 3 4734 1 1 2 1921 3430 3373 1 3805 3909 56118 23383 2 1471 2065 23679 2 1052 1154 30740 1 1098 2180 13716 29728 1 1094 3585 2073 93894 1 2024 4201 39023 1713 3 1571 21453 96893 3 1297...
output:
0 7262943486 185110624 53327400 957813600 383014415 1539405803 896522316 1454164560 7158196459 479198625 1943839360 1189657450 23355822139 2684778350 183742084 6400082784 2310401225 2082631008 5644811789 1875949890 3185562597 7185156304 3147144197 1588457333 676240200 1122598010 8758314557 100699296...
result:
ok 1663 numbers
Test #5:
score: 18
Accepted
time: 131ms
memory: 49664kb
input:
4944 4934 1 468 4845 87517 63656 3 4756 22899 79177 1 761 1054 45331 86403 1 24 2806 46189 11490 1 2602 4446 12528 14317 3 2601 51537 65051 1 1502 3573 79699 84830 3 1998 35405 151264 1 2400 4041 95071 83748 1 2050 3772 23643 53614 3 2261 51072 236192 2 1317 1908 6197 2 949 2543 30190 1 1457 4573 33...
output:
3582496024 860310840 5337461878 10833286574 1397502876 3735482073 4207877274 17671620 10854427218 1484917319 5462491276 1497165465 1453546510 1672688712 1158344316 1014734250 3797802047 15668090927 14634073116 32337553147 2159971110 12088416736 90924880 1410366456 13829776128 12126485158 18393654569...
result:
ok 829 numbers
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 30ms
memory: 7884kb
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 13875 68164 8551 37356 51678 78688 9772 17674 28663 11002 102350 18755 36993 229473 61114 309657 445575 67332 280040 41468 565383 14241 245087 151356 35296 139339 108738 174373 21036 290401 205700 405809 35460 43749 209279 494612 42184 624800 245616 672241 71368 774313 1002309 259392 236613 8906...
result:
wrong answer 3rd numbers differ - expected: '1254619125', found: '13875'
Subtask #3:
score: 16
Accepted
Test #12:
score: 16
Accepted
time: 34ms
memory: 7940kb
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: 16
Accepted
time: 31ms
memory: 7892kb
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: 16
Accepted
time: 26ms
memory: 7920kb
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: 16
Accepted
time: 33ms
memory: 7760kb
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: 16
Accepted
time: 31ms
memory: 7876kb
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: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 33ms
memory: 7928kb
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 89644 0 0 586692 52542 0 113738 113738 105774 113738 336593 0 63627 327136 290548 0 220294 137888 78268 58519 108806 0 84171 110920 11181 0 262388 189704 340745 183158 60159 330620 266786 200713 120333 292978 189222 99905 68739 0 0 302890 170639 84927 203028 8521 150941 0 0 0 10004 102049 0 168532...
result:
wrong answer 2nd numbers differ - expected: '34602584', found: '89644'
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%