QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #804134 | #1458. Binary Search Algorithm | eggegg185 | WA | 2ms | 4536kb | C++14 | 1.3kb | 2024-12-07 20:36:16 | 2024-12-07 20:36:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n,ask[100010],res[100010],cnt = 0;
struct segT {
int mi[200010];
segT() {memset(mi,-1,sizeof(mi));}
void pp(int u,int c,int k = 1,int l = 1,int r = n) {
if(l == r) {if(c == 1) ask[++cnt] = u; return ;}
int mid = (l+r)>>1; if(u <= mid) {pp(u,c,mid<<1,l,mid); if(mi[mid<<1|1] != -1) ask[++cnt] = mi[mid<<1|1];}
else {pp(u,c,mid<<1|1,mid+1,r); if(mi[mid<<1] != -1) ask[++cnt] = mi[mid<<1];}
}
void modify(int u,int c,int k = 1,int l = 1,int r = n) {
if(l == r) {mi[k] = c; return ;}
int mid = (l+r)>>1; if(u <= mid) modify(u,c,mid<<1,l,mid);
else modify(u,c,mid<<1|1,mid+1,r);
if(mi[mid<<1|1] == -1) {mi[k] = mi[mid<<1]; return ;}
if(mi[mid<<1] == -1) {mi[k] = mi[mid<<1|1]; return ;}
if(res[mi[mid<<1]] < res[mi[mid<<1|1]]) mi[k] = mi[mid<<1];
else mi[k] = mi[mid<<1|1];
}
}tt;
char s[10];
int main() {
//cin.tie(0)->sync_with_stdio(false);
scanf("%d",&n); for(int i = 1; i <= 2*n; i++) {
int x; scanf("%s%d",s+1,&x);
cnt = 0; tt.pp(x,(s[1]=='a')?1:(-1)); sort(ask+1,ask+1+cnt); cnt = unique(ask+1,ask+1+cnt)-ask-1;
cout << cnt << ' '; for(int i = 1; i <= cnt; i++) cout << ask[i] << ' '; cout << endl;
for(int i = 1; i <= cnt; i++) scanf("%d",&res[ask[i]]);
tt.modify(x,(s[1]=='a')?x:(-1)); cout << tt.mi[1] << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4452kb
input:
3 add 1 1 add 3 3 1 delete 1 3 add 2 3 2 delete 3 2 delete 2
output:
1 1 1 2 1 3 3 1 3 3 2 2 3 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 4536kb
input:
10 add 9 9 add 4 9 4 add 6 9 4 6 delete 9 4 6 add 7 7 4 6 delete 4 6 add 5 5 6 add 8 5 8 6 add 10 10 5 8 delete 8 10 5 6 add 3 3 5 6 add 2 3 5 6 2 delete 6 7 10 2 delete 10 7 2 delete 7 2 add 1 3 1 5 2 delete 1 3 5 2 delete 3 5 2 delete 5 2 delete 2
output:
1 9 9 2 4 9 9 3 4 6 9 6 2 4 6 4 3 4 6 7 6 1 6 6 2 5 6 5 3 5 6 8 5 3 5 8 10 8 3 5 6 10 6 3 3 5 6 3 4 2 3 5 6 6 3 2 7 10 10 2 2 7 7 1 2 2 4 1 2 3 5 2 3 2 3 5 5 2 2 5 5 1 2 2 0 -1
result:
wrong answer WA after query 3 found 6, answer is 9