QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331619#8226. 堆操作练习题2djwj23330 6ms34788kbC++142.4kb2024-02-18 15:57:322024-02-18 15:57:35

Judging History

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

  • [2024-05-22 20:40:58]
  • hack成功，自动添加数据
  • (/hack/631)
  • [2024-02-18 15:57:35]
  • 评测
  • 测评结果：30
  • 用时：6ms
  • 内存：34788kb
查看
  • [2024-02-18 15:57:32]
  • 提交

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 ll P = 1e9 + 7;
const int N = 3e5 + 10, QMAX = 5e5 + 10, M = 1e6 + 10;

int h, n, arr[N], a[N];
struct query {  int o, x, y;  } q[QMAX];
ll ans[N], pw[N]; vector<int> V[N], des[N];

int val[N], tmp[M], mark[M], pos[N];
struct Fenwick {
    int s, b[N];
    void reset(int now) {  s = now; fo(i, 1, now) b[i] = 0;  }
    void add(int x, int C) {
        for(; x <= s; x += x & -x) b[x] += C;
    }
    int ask(int x) {
        int res = 0; for(; x; x -= x & -x) res += b[x];
        return res;
    }
} F[3];

int opr(int x) {
    a[x] = 0;
    while((x << 1) <= n && a[x << 1] + a[x << 1 | 1] > 0) {
        if(a[x << 1] > a[x << 1 | 1])
            swap(a[x], a[x << 1]), x = (x << 1);
        else
            swap(a[x], a[x << 1 | 1]), x = (x << 1 | 1);
    }
    return x;
}

int main()
{
    scanf("%d", &h), n = (1 << h) - 1;
    fo(i, 1, n) {
        scanf("%d", &arr[i]);
        int p = i; while(p) des[p].push_back(i), p >>= 1;
    }
    pw[0] = 1; fo(i, 1, n) pw[i] = 2 * pw[i - 1] % P;

    int Q; scanf("%d", &Q);
    fo(i, 1, Q) {
        scanf("%d%d%d", &q[i].o, &q[i].x, &q[i].y);
        int p = q[i].x; if(q[i].o == 3) {  V[p].push_back(i); continue;  }
        while(p) V[p].push_back(i), p >>= 1;
    }

    fo(i, 1, n) {
        int m = 0, sum = 0;
        for(int x : des[i]) m++, val[m] = a[x] = arr[x];
        sort(val + 1, val + m + 1);
        fo(j, 1, m) tmp[val[j]] = j, mark[val[j]] = i;

        int cnt = 0; while(a[i]) pos[opr(i)] = ++cnt;
        F[1].reset(m), F[2].reset(m);
        for(int id : V[i]) {
            if(q[id].o == 1) {
                F[q[id].y].add(pos[q[id].x], 1), sum += (q[id].y == 2);
            } else if(q[id].o == 2) {
                F[q[id].y].add(pos[q[id].x], -1), sum -= (q[id].y == 2);
            } else {
                if(mark[q[id].y] != i) {  ans[id] = 0; continue;  }
                int p = m - tmp[q[id].y] + 1, u = F[1].ask(p), v = F[2].ask(p);
                if(F[1].ask(p - 1) == 0 && (u == 1 || (v - F[2].ask(p - 1)) == 1))
                    ans[id] = pw[sum - v];
            }
        }
    }

    fo(i, 1, Q) if(q[i].o == 3) printf("%lld\n", ans[i]);

    return 0;
}
/*
 
*/
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 3ms
memory: 32564kb

input:

2
3 2 1
50
3 3 1
1 1 2
1 2 1
2 2 1
1 2 2
2 1 2
1 1 1
1 3 2
2 1 1
2 2 2
3 1 2
3 1 3
2 3 2
1 3 2
1 2 2
2 2 2
1 2 1
1 1 2
3 1 1
2 1 2
1 1 1
2 1 1
3 1 2
3 1 3
2 3 2
1 3 2
2 2 1
1 2 1
1 1 1
3 1 2
2 1 1
1 1 1
3 3 1
2 1 1
2 3 2
1 3 1
2 3 1
1 1 2
3 1 3
2 1 2
3 3 1
3 1 3
3 1 1
3 1 1
1 3 2
1 1 1
2 1 1
3 1 1
2...

output:

0
1
0
0
0
2
0
1
2
0
1
0
0
0
0

result:

ok 15 numbers

Test #2:

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

input:

2
3 1 2
50
1 2 2
3 3 2
2 2 2
1 3 1
1 1 1
3 3 2
2 1 1
3 1 3
2 3 1
1 3 1
1 1 1
1 2 2
2 1 1
3 1 3
2 3 1
2 2 2
1 1 2
1 2 1
1 3 1
2 1 2
3 3 2
1 1 1
2 3 1
1 3 2
2 3 2
1 3 1
2 2 1
3 3 2
3 1 1
2 3 1
2 1 1
1 3 1
2 3 1
3 1 3
3 1 3
3 1 3
1 1 1
2 1 1
3 1 2
1 2 1
3 1 1
3 3 2
3 1 3
2 2 1
1 1 1
2 1 1
1 2 1
1 1 2
2...

output:

0
1
1
2
1
1
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 32488kb

input:

4
15 14 13 9 10 11 12 2 7 4 5 1 6 8 3
500
3 1 15
3 1 13
1 9 1
1 6 2
1 15 2
1 14 1
1 10 2
1 5 2
3 12 1
1 1 1
1 4 1
3 6 6
3 10 4
1 3 1
3 13 6
1 11 2
2 4 1
2 14 1
3 6 6
3 1 11
3 1 14
3 2 4
2 6 2
2 15 2
3 1 9
3 7 12
1 13 2
2 9 1
2 5 2
3 14 8
1 15 2
1 12 1
3 11 5
1 5 2
3 1 15
3 5 10
3 1 11
1 14 1
2 13 2
...

output:

0
0
0
0
1
0
0
8
0
0
0
0
0
1
16
4
0
0
0
8
0
0
1
8
0
0
16
0
0
0
0
4
0
0
0
0
1
0
0
0
0
0
8
1
0
128
0
0
0
2
1
16
0
64
4
0
0
0
2
1
2
0
1
0
0
0
0
2
1
16
0
0
1
0
1
4
0
0
2
0
2
0
0
2
4
0
1
0
1
1
0
4
0
0
0
0
1
0
0
0
1
0
0
0
0
0
4
1
0
0
0
1
1
0
0
0
0
1
1
4
0
1
1
1
1
0
1
1
1
1
0
0
4
0
0
0
0
0
0
1
2
1
2
1
0
4
0...

result:

wrong answer 5th numbers differ - expected: '8', found: '1'

Subtask #3:

score: 20
Accepted

Test #5:

score: 20
Accepted
time: 4ms
memory: 32604kb

input:

9
511 509 510 504 507 505 508 501 503 506 502 494 500 499 493 473 483 495 475 491 497 461 487 490 489 498 496 478 485 480 488 378 469 482 477 462 448 422 470 424 467 421 492 439 454 484 451 376 385 458 464 463 486 411 472 449 474 459 468 479 413 457 455 371 315 432 437 466 453 476 418 433 363 434 38...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
1
1
...

result:

ok 1644 numbers

Test #6:

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

input:

9
511 510 506 509 508 505 504 500 507 501 503 497 498 502 484 454 495 485 494 488 496 493 474 491 460 487 490 486 499 468 467 408 448 451 469 479 478 412 492 482 476 440 466 489 411 462 470 384 407 438 452 430 464 439 481 456 483 449 422 420 446 441 370 372 376 404 443 369 417 405 416 465 444 275 45...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
1
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
0
0
0
0
1
...

result:

ok 1657 numbers

Test #7:

score: 0
Accepted
time: 6ms
memory: 34664kb

input:

9
511 508 510 502 505 506 509 497 489 501 504 496 500 507 499 494 486 466 482 472 442 503 453 492 469 481 477 488 491 483 484 493 416 480 485 420 465 436 471 353 447 437 384 490 498 399 381 487 468 461 457 478 479 474 473 248 430 412 448 429 421 449 475 423 476 338 410 435 444 438 462 379 415 372 39...

output:

0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
0
1
0
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
...

result:

ok 1644 numbers

Test #8:

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

input:

9
511 509 510 505 506 508 490 499 484 497 501 507 504 477 481 494 469 479 468 458 486 496 487 503 495 498 449 461 467 476 480 448 470 424 459 413 478 441 466 429 446 485 438 489 463 473 483 502 500 491 492 474 493 443 430 385 433 453 447 460 472 379 408 363 415 367 445 401 405 426 259 383 351 322 45...

output:

0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
0
1
1
...

result:

ok 1620 numbers

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Test #13:

score: 0
Time Limit Exceeded

input:

18
262143 262142 262141 262135 262134 262140 262137 262119 262122 262133 262117 262136 262139 262129 262130 262114 262088 262099 262080 262126 262131 262091 262101 262128 262132 262138 262115 262103 262121 262069 262094 262111 262078 261968 262042 262032 262097 262059 262074 262086 262113 262124 262...

output:

result:

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-02 18:51:30 | 開源專案