QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#804123 | #1458. Binary Search Algorithm | eggegg185 | RE | 0ms | 0kb | C++14 | 1.3kb | 2024-12-07 20:32:42 | 2024-12-07 20:32:43 |
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 k = 1,int l = 1,int r = n) {
if(l == r) {ask[++cnt] = u; return ;}
int mid = (l+r)>>1; if(u <= mid) {pp(u,mid<<1,l,mid); if(mi[mid<<1|1] != -1) ask[++cnt] = mi[mid<<1|1];}
else {pp(u,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); 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: 0
Runtime Error
input:
3 add 1