QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253312#3300. Cactus Competitiondjwj233WA 4ms22392kbC++142.4kb2023-11-16 21:13:472023-11-16 21:13:48

Judging History

你现在查看的是最新测评结果

  • [2023-11-16 21:13:48]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:22392kb
  • [2023-11-16 21:13:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v = a; v <= b; v++)
#define fr(v,a,b) for(int v = a; v >= b; v--)
#define cl(a,v) memset(a, v, sizeof(a))

typedef long long ll;

const int INF = 1e9 + 7;
const int N = 1e6 + 10;

int n, m, A[N], B[N], mx, mn;
int st[N], top, pos[N], gap[N], cnt;

priority_queue<pair<int, int>, vector<pair<int, int> >,
    greater<pair<int, int> > > Q;

void Solve(bool fl, int *arr) {
    top = cnt = 0, cl(st, 0), cl(pos, 0), cl(gap, 0);
    while(Q.size()) Q.pop();

    mx = -INF, mn = INF;
    fo(i, 1, m) mx = max(mx, B[i]), mn = min(mn, B[i]);

    fo(i, 1, m) if(top == 0 || B[i] > B[st[top]])
        st[++top] = i;
    pos[cnt = 1] = 1, gap[1] = B[1];
    fo(i, 2, top) {
        int z = INF;
        fo(j, st[i - 1] + 1, st[i]) z = min(z, B[j]);
        if(gap[i - 1] <= z) pos[cnt] = st[i];
        else pos[++cnt] = st[i], gap[cnt] = z;
    }

    fo(i, 1, n) {
        if(A[i] + mx < 0) {
            while(Q.size()) Q.pop();
            continue;
        }
        if(A[i] + B[1] < 0) {
            int l = 1, r = cnt, mid;
            while(l < r) {
                mid = (l + r) >> 1;
                if(A[i] + B[pos[mid]] < 0) l = mid + 1;
                else r = mid;
            }
            while(Q.size() && Q.top().first < l) Q.pop();
        } else {
            Q.push(make_pair(1, 1));
            int l = 1, r = cnt, mid;
            while(l < r) {
                mid = (l + r + 1) >> 1;
                if(A[i] + gap[mid] >= 0) l = mid;
                else r = mid - 1;
            }
            int cur = 0;
            while(Q.size() && Q.top().first <= l)
                cur += Q.top().second, Q.pop();
            if(cur) Q.push(make_pair(l, cur));
        }
        if(A[i] + mn >= 0) {
            assert(Q.top().first == cnt);
            arr[i] = Q.top().second;
            if(fl) while(Q.size()) Q.pop();
        }
    }
}

int preCnt[N], sufCnt[N]; ll ans;

int main()
{
    // freopen("travel6.in", "r", stdin);

    scanf("%d%d", &n, &m);
    fo(i, 1, n) scanf("%d", &A[i]);
    fo(i, 1, m) scanf("%d", &B[i]);

    Solve(false, preCnt);
    reverse(A + 1, A + n + 1), reverse(B + 1, B + m + 1);
    Solve(true, sufCnt);

    fo(i, 1, n) ans += (ll)preCnt[i] * sufCnt[n - i + 1];
    printf("%lld\n", ans);

    return 0;
}
/*
 
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22388kb

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 20184kb

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 3ms
memory: 20272kb

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: 22320kb

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: 3ms
memory: 20148kb

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: 3ms
memory: 22252kb

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: 3ms
memory: 22312kb

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: 4ms
memory: 22384kb

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: 20280kb

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: 20272kb

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: 3ms
memory: 22324kb

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: 0ms
memory: 20200kb

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: 18200kb

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: 3ms
memory: 20336kb

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: 22196kb

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: 0ms
memory: 22308kb

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: 3ms
memory: 20284kb

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: 0ms
memory: 20188kb

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: 22384kb

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: 3ms
memory: 22196kb

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: -100
Wrong Answer
time: 0ms
memory: 22392kb

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:

9

result:

wrong answer 1st lines differ - expected: '6', found: '9'