68pts TLE+WA 求优化
  • 板块P11186 三目运算
  • 楼主heyZZZ
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/13 13:03
  • 上次更新2024/10/13 15:03:16
查看原帖
68pts TLE+WA 求优化
1015977
heyZZZ楼主2024/10/13 13:03
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,p,n,tot,t,ans;
string s;
stack<int> sk;
struct tree{
	int l,r,fg,x;
}a[1000005];
void dfs(int x){
	if(a[x].fg==1){
		if(t>a[x].x) dfs(a[x].l);
		else dfs(a[x].r);
	}
	if(a[x].fg==-1){
		if(t<a[x].x) dfs(a[x].l);
		else dfs(a[x].r);
	}
	if(!a[x].fg){
		ans=a[x].x;
		return;
	}
}
signed main(){
	// freopen("expr.in","r",stdin);
	// freopen("expr.out","w",stdout);
	cin>>m>>p>>s,n=s.size();
	for(int i=1;i<n;i++){
		if(s[i]=='<') a[++tot].fg=-1;
		if(s[i]=='>') a[++tot].fg=1;
		if(s[i]<='9'&&s[i]>='0'){
			if(s[i-1]=='<'||s[i-1]=='>'||(s[i-1]<='9'&&s[i-1]>='0')) a[tot]={-1,-1,a[tot].fg,a[tot].x*10+s[i]-48};
			else a[++tot]={-1,-1,a[tot].fg,a[tot].x*10+s[i]-48};
		}
		if(s[i]=='?') a[tot].l=tot+1,sk.push(tot);
		if(s[i]==':'){
			a[sk.top()].r=tot+1,sk.pop();
		}
	}
	while(p--){
		cin>>t,ans=0;
		dfs(1),cout<<ans<<'\n';
	}
	return 0;
}

2024/10/13 13:03
加载中...