QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1435 | #848065 | #8226. 堆操作练习题2 | little_one | little_one | Success! | 2025-01-08 15:21:06 | 2025-01-08 15:21:07 |
詳細信息
Extra Test:
Time Limit Exceeded
input:
18 262143 262142 262141 262140 262139 262138 262137 262136 262135 262134 262133 262132 262131 262130 262129 262128 262127 262126 262125 262124 262123 262122 262121 262120 262119 262118 262117 262116 262115 262114 262113 262112 262111 262110 262109 262108 262107 262106 262105 262104 262103 262102 262...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #848065 | #8226. 堆操作练习题2 | little_one | 97 | 399ms | 66972kb | C++14 | 1.9kb | 2025-01-08 15:08:15 | 2025-01-08 15:25:01 |
answer
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int p = 1000000007;
int h,q,aa[262144],a[262144],typ[262144],cnt,o1,o2,o3,pw[262144];
vector <int> val[262144],pos[262144];
int del(int x){
if(x >= (1 << (h - 1)) || (!a[x << 1] && !a[x << 1 | 1])){
a[x] = 0;
return x;
}
if(a[x << 1] > a[x << 1 | 1]){
swap(a[x],a[x << 1]);
return del(x << 1);
}
swap(a[x],a[x << 1 | 1]);
return del(x << 1 | 1);
}
void cpy(int x){
a[x] = aa[x];
if(x < (1 << (h - 1))){
cpy(x << 1);
cpy(x << 1 | 1);
}
}
void dfs(int x){
cpy(x);
while(a[x]){
val[x].push_back(a[x]);
pos[x].push_back(del(x));
}
if(x < (1 << (h - 1))){
dfs(x << 1);
dfs(x << 1 | 1);
}
}
int main(){
scanf("%d",&h);
pw[0] = 1;
for(int i = 1;i < (1 << h);i++){
scanf("%d",&aa[i]);
pw[i] = (pw[i - 1] << 1) % p;
}
dfs(1);
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&o1,&o2,&o3);
if(o1 == 1){
typ[o2] = o3;
if(o3 == 2){
cnt++;
}
}
else if(o1 == 2){
typ[o2] = 0;
if(o3 == 2){
cnt--;
}
}
else{
bool flag = 0;
int c = cnt;
for(int i = 0;i < val[o2].size();i++){
c -= (typ[pos[o2][i]] == 2);
if(val[o2][i] == o3){
flag = typ[pos[o2][i]];
break;
}
if(typ[pos[o2][i]] == 1){
break;
}
}
if(flag){
printf("%d\n",pw[c]);
}
else{
printf("0\n");
}
}
}
return 0;
}