QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357729 | #3300. Cactus Competition | wdnmdwrnmmp | WA | 1ms | 5888kb | C++14 | 1.6kb | 2024-03-19 09:56:36 | 2024-03-19 09:56:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
const int N=2e5+5,inf=1e9+5;
int n,m,a[N],b[N];
int s[N][2];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
rep(i,1,n){
cin>>a[i];
}
rep(i,1,m){
cin>>b[i];
}
// rep(i,1,n){
// rep(j,1,m){
// cout<<(a[i]+b[j]>=0);
// }
// cout<<'\n';
// }
int mn=*min_element(b+1,b+m+1);
vi stk;
rep(i,1,n){
int ls=0;
while(!stk.empty() && a[stk.back()]<=a[i]){
ls=stk.back();
stk.pop_back();
}
if(!stk.empty()){
s[stk.back()][1]=i;
}
s[i][0]=ls;
stk.pb(i);
}
long long ans=0;
auto dfs=[&](auto self,int u,int L,int R)->void{
if(!u){
return;
}
if(mn+a[u]<0){
return;
}
int le=1,ri=1;
int mnl=a[u],mnr=a[u];
per(i,u-1,L){
mnl=min(mnl,a[i]);
int mx=-inf;
rep(j,1,m){
if(a[i]+b[j]<0){
break;
}
mx=max(mx,b[j]);
}
if(mx+mnl>=0){
le++;
}
}
rep(i,u+1,R){
mnr=min(mnr,a[i]);
int mx=-inf;
per(j,m,1){
if(a[i]+b[j]<0){
break;
}
mx=max(mx,b[j]);
}
if(mx+mnr>=0){
ri++;
}
}
// cout<<u<<' '<<le<<' '<<ri<<endl;
ans+=(long long)le*ri;
self(self,s[u][0],L,u-1);
self(self,s[u][1],u+1,R);
};
// cout<<"?"<<stk[0]<<' '<<a[stk[0]]<<endl;
dfs(dfs,stk[0],1,n);
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
3 3 -1 0 1 -1 0 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5636kb
input:
3 3 -1 0 1 1 0 1
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 10 145195799 312862766 143966779 -11056226 -503624929 636383890 -182650312 -382759112 -290767690 377894950 -845235881 -418232930 -600566938 -957917357 -181139226 125255273 -175406945 740226783 -750456842 325848662
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 10 923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590 553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615
output:
13
result:
ok single line: '13'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
10 10 -123276196 264891802 609485405 -980113903 152483893 57563748 -454135131 618686452 545983457 236619926 648896419 838269531 -380077537 536463844 89691984 38425645 759165084 325716532 330825142 -472414030
output:
12
result:
ok single line: '12'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
10 10 982508669 144806400 -503165973 760719995 -249757698 -573349946 -974145393 -905114292 218260516 -582308724 -341366248 187422683 298181900 -305351333 -616330465 -358958909 499163196 -967112195 -892547772 -605274022
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 10 -46634296 998649898 637256009 858343376 -339756903 750734027 533317110 509238419 -386390857 573123021 281094131 -798662878 454769235 -725579556 448648301 -937460999 -94310392 -504422439 -566805692 -883657655
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5544kb
input:
10 10 -448680004 -918586552 -352190179 959516158 674275159 -778874335 -736749389 -368418013 103878020 562512923 -493932809 -736960513 78543198 885372691 -119140562 627952281 733778437 115556860 -196686999 -530143800
output:
3
result:
ok single line: '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 5576kb
input:
10 10 438736217 -79057408 749090846 -106479211 -864134653 49806870 -724192950 -354806728 -230893984 130090227 -313678558 -493317070 -704907097 -240066585 275905249 -440144088 -697190358 608351624 783121279 -54163556
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 10 910467973 475480237 284540173 -490003419 -496858639 575308046 -772115835 -650286781 -946294433 -375903216 465208966 198897340 37926241 -452764487 81169636 803610511 943188813 773420180 248487883 -932609634
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
10 10 -717662422 899539843 686516865 -308859590 731187727 948271874 -278705921 533338789 378708586 -53953529 -819295682 -712753496 -588162402 -765119207 518537239 793210677 199564253 443460314 248599384 333581283
output:
14
result:
ok single line: '14'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
10 10 13154473 419018121 -416088051 751464183 -782740304 257733919 -917880927 -690282918 410240353 817939924 440852087 -846511822 -519300757 153508300 757901474 928246448 -132837037 -603019187 860960474 -381787006
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
10 10 -357608489 679822152 25019791 265926477 -309098231 -7866110 -344995594 54868813 319830921 627547981 -431127028 -396320203 -35574917 657270168 -452580497 -359511978 -443174072 195670048 -696354158 2633147
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
10 10 126298083 -169291689 736314121 784469908 642788743 -450191333 -98804016 -511077469 -691147937 -275067405 440527703 -329746015 -473928781 -114255013 -450714278 -903623369 888225605 -146644734 173060316 214649350
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 5588kb
input:
10 10 -631748556 73286407 324751086 157696597 846447361 -444570059 484021795 -258058046 -116283058 -158063251 712663587 -233692952 820220037 516771553 879333593 156354440 -36643636 -639052753 -790959020 950256682
output:
30
result:
ok single line: '30'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
20 10 -623445264 -424346675 38726811 -683309080 312098721 491569101 58067873 265188450 933087599 -786006093 -652539909 -790632832 780472328 -854541037 -851647529 130095820 35107516 -49396621 -476857996 -420750398 102904427 387758770 -297785914 -909492241 54351476 480814965 -450898650 532245762 14578...
output:
5
result:
ok single line: '5'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
20 10 -896420596 -203318573 177883279 273218889 -57519747 -45966158 -776510191 -517769446 453200208 481678849 182234053 -9041974 599680026 114185708 -42217888 -909337940 901125545 -573238491 923694668 317307691 -39965725 441117134 808874018 742445820 195129663 -895470087 -362043267 -116187269 768684...
output:
5
result:
ok single line: '5'
Test #18:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
20 10 -353233765 531419122 -565785466 -974734316 -965779178 -574407138 -468557050 143840293 -215604312 -616224273 -898730647 860935752 160786259 790117305 493435217 142732932 -298131838 151928054 -491642434 354879620 -793096213 -805492095 -608815122 348634111 -671513949 992581086 -838707020 58016785...
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
20 10 -701460484 808554993 -999153824 -785817990 -733107864 102913155 -574790819 366838774 386927511 368140655 -817331097 -532497190 -875689404 26653738 514253474 -613613559 138082391 199526495 -340809187 -265988736 139281656 -212060959 990432379 509453538 322401348 415039202 713351409 656821225 -37...
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
20 10 283365694 154990137 -35366598 -650189405 -536760259 988010949 -588839879 419138587 473855117 783095177 -727335506 -711138940 688902025 848042392 -418956949 -551400268 -445912306 328186693 902566329 -781464261 -151440066 304048484 39686192 -66659263 690407227 450204900 21929380 -636199785 -2908...
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
20 30 237952402 -335139165 -955671638 -412642356 -480102753 -346638667 993109413 -711571417 653077878 434015585 670459996 -463458168 -861206961 -564606372 575461609 276985893 624287505 990687478 -356864944 -323862739 -65141151 -910501868 964552356 987340218 98190644 -533295887 -628531995 104796764 -...
output:
6
result:
ok single line: '6'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
20 30 422573927 -99296392 66641971 -467451544 -929697025 987635538 -823741408 -282328894 667795417 403667640 77855317 768938833 851375837 -482238764 535050604 693284244 665832562 -414334930 282053424 841142538 625401169 -873800421 -295606036 -563876252 -486871726 658432653 -540621613 83171505 -32868...
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
20 30 -296660442 -406371023 -7219650 -696407112 -541274666 -13649953 -547746165 103748569 -811509150 -852033818 161353366 477631703 -132349977 -867850711 -343436602 -864191995 664531962 642517117 995654422 -843941103 57878945 715837144 219107402 -746771795 -658539543 949649650 -896370803 86006348 -2...
output:
3
result:
ok single line: '3'
Test #24:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
20 30 -192624362 460020584 -130262590 -935952369 387086405 -811490574 575282127 -586968948 446945051 392426524 -602685180 954542768 -996079654 92931412 94702743 -358819889 89519102 891193603 534434457 -996719580 403561450 703364521 939494115 -839657656 684830582 235050720 -245163297 761982957 295950...
output:
0
result:
ok single line: '0'
Test #25:
score: -100
Wrong Answer
time: 1ms
memory: 3496kb
input:
20 30 984062212 -888911800 -729112541 940614685 -541773420 605970812 -230912033 340003650 340985629 143521592 -386427316 -31856346 808873635 274103528 233430835 772424780 -655550174 669911837 735705463 526705066 790185048 -638066905 -983213910 570408047 -896905178 85016777 -878189921 670518427 -4579...
output:
4
result:
wrong answer 1st lines differ - expected: '5', found: '4'