求助大佬,肝了一下午,全部wa了
查看原帖
求助大佬,肝了一下午,全部wa了
363495
我爱杨帆楼主2020/10/13 17:09
#include<bits/stdc++.h>
using namespace std;
struct tree
{
	int l,r,dat;
}t[40000000];
struct tree1
{
	int l1,r1,dat1;
}t1[40000000];
struct year
{
	int pos,rain,year;
}y[4000000];
#define l(p) t[p].l
#define r(p) t[p].r
#define mul(p) t[p].mul
#define dat(p) t[p].dat
#define l1(p) t1[p].l1
#define r1(p) t1[p].r1
#define mul1(p) t1[p].mul1
#define dat1(p) t1[p].dat1
int rain1[500000],rain2[500000];
int read()
{
	char c;
	int f=1,r=0;
	c=getchar();
	while(c!='-'&&(c<'0'||c>'9'))
	c=getchar();
	if(c=='-')
	{
	f=-1;
    c=getchar();
	}
	while(c>='0'&&c<='9')
	{
	r=r*10+c-'0';
    c=getchar();
	}
	return r*f;
}	
void build(int p,int l,int r)
{   
    l(p)=l,r(p)=r;
  	if(l==r)
  	{
  	 dat(p)=rain1[l];
	 return;	
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	dat(p)=max(dat(2*p),dat(2*p+1)); 
}
int ask_dat(int p,int l,int r)
{
 if(l<=l(p)&&r>=r(p))
 return dat(p);
 int mid=(l(p)+r(p))/2;
 int ans=0;
 if(l<=mid)
 ans=max(ask_dat(2*p,l,r),ans);
 if(r>mid)
 ans=max(ans,ask_dat(2*p+1,l,r));
 return ans;	
} 
void build1(int p,int l,int r)
{   
    l1(p)=l,r1(p)=r;
  	if(l==r)
  	{
  	 dat1(p)=rain2[l];
	 return;	
	}
	int mid=(l+r)/2;
	build1(2*p,l,mid);
	build1(2*p+1,mid+1,r);
	dat1(p)=max(dat1(2*p),dat1(2*p+1)); 
}
int ask_dat1(int p,int l,int r)
{
 if(l<=l1(p)&&r>=r1(p))
 return dat1(p);
 int mid=(l1(p)+r1(p))/2;
 int ans=0;
 if(l<=mid)
 ans=max(ask_dat1(2*p,l,r),ans);
 if(r>mid)
 ans=max(ans,ask_dat1(2*p+1,l,r));
 return ans;	
}	
int n=read(),tot=1;
int erfen(int yy)
{
  int l=1,r=n;
  int ans=0;
  while(l<=r)
  {
  int mid=(l+r)/2;	
  if(y[mid].year>=yy)
  {
	ans=mid;
   	r=mid-1;
  }
  else
  l=mid+1;	
  }
  return ans;
}
int main()
{
	memset(rain1,24,sizeof(rain1));
	y[1].year=read();
	y[1].pos=1;
	y[1].rain=read();
	rain1[1]=y[1].rain;
	rain2[1]=rain1[1];
	for(int i=2;i<=n;i++)
	{         
	  	y[i].year=read();
	  	if(y[i].year-1==y[i-1].year)
	  	{     
		rain1[tot+1]=read();
		y[i].rain=rain1[tot+1];
	  	rain2[tot+1]=rain1[tot+1];
	  	tot++;
	  	y[i].pos=tot;
	    }
	    else
	    {
	    rain1[tot+2]=read();
	    y[i].rain=rain1[tot+2];
		rain2[tot+2]=rain1[tot+2];
		tot+=2;
		y[i].pos=tot;	
		}
	} 
	build(1,1,tot);
	build1(1,1,tot);
	int m=read();
	for(int i=1;i<=m;i++)
	{
		int y1=read(),y2=read();
		int pos1=erfen(y1),pos2=erfen(y2);
		if(ask_dat1(1,y[pos1].pos+1,y[pos2].pos)!=rain1[y[pos2].pos])
		{
		cout<<"false"<<endl;
		continue;
	    }
		if(ask_dat1(1,y[pos1].pos+1,y[pos2].pos)==rain1[y[pos2].pos]&&ask_dat(1,
		y[pos1].pos+1,y[pos2].pos)==404232216)
		{
		cout<<"maybe"<<endl;
		continue;	
		}
		if(ask_dat(1,y[pos1].pos+1,y[pos2].pos)==rain1[y[pos2].pos])
		{
		cout<<"true"<<endl;	
		continue;	
		}
	}
}
2020/10/13 17:09
加载中...