Submission #1734759

---

Source Code Expand

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[1100000];
int to[1100000][27];
vector<int>g[1100000];
int segtree[1<<22];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return mod;
	if(c<=a&&b<=d)return segtree[e];
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=(1<<21);
	while(a){
		segtree[a]=min(segtree[a],b);
		a/=2;
	}
}
int rev[1100000];
int val[1100000];
int eu[2100000];
int fi[1100000];
int num;
int sz;
void dfs(int a){
	val[a]=num;
	rev[num++]=a;
	fi[a]=sz;
	eu[sz++]=val[a];
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i]);
		eu[sz++]=val[a];
	}
}
int h[1100000];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	int a;scanf("%d",&a);
	for(int i=0;i<27;i++)to[n][i]=-1;
		//printf("%d: %d %d %d\n",n,to[n][24],to[n][25],to[n][26]);
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<27;j++){
			if(in[i]>'a'+j){
				to[i][j]=-1;
				continue;
			}
			if(in[i]=='a'+j){
				to[i][j]=i+1;
			}else{
				if(to[i][j-1]!=-1&&to[to[i][j-1]][j-1]!=-1)to[i][j]=to[to[i][j-1]][j-1];
				//else if(to[i][26]!=-1)to[i][j]=to[to[i][26]][j];
				else to[i][j]=-1;
			}
		}
		for(int j=0;j<26;j++){
			if(to[i][j]==-1&&to[i][26]!=-1)to[i][j]=to[to[i][26]][j];
		}
		//printf("%d: %d %d %d\n",i,to[i][24],to[i][25],to[i][26]);
		if(~to[i][26]){
			h[i]=1;
			g[to[i][26]].push_back(i);
		}
	}
	for(int i=0;i<(1<<22);i++)segtree[i]=mod;
	for(int i=0;i<=n;i++){
		if(h[i]==0)g[n+1].push_back(i);
	}
 
	dfs(n+1);
	for(int i=0;i<sz;i++)update(i,eu[i]);
 
	while(a--){
		int p,q;scanf("%d%d",&p,&q);
		p--;
		int at=rev[query(0,(1<<21)-1,min(fi[p],fi[q]),max(fi[p],fi[q]),1)];
		//printf("%d %d: %d\n",p,q,at);
		if(at==p||at==q){
			printf("Yes\n");
		}else printf("No\n");
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",in);
                ^
./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int a;scanf("%d",&a);
                      ^
./Main.cpp:86:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int p,q;scanf("%d%d",&p,&q);
                              ^

Judge Result