首页 > 代码库 > bzoj 1067: [SCOI2007]降雨量 模擬

bzoj 1067: [SCOI2007]降雨量 模擬

1067: [SCOI2007]降雨量

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2010  Solved: 503
[Submit][Status]

Description

我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知,有的说法是可能正确也可以不正确的。

Input

输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

对于每一个询问,输出true,false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

 

100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

 

Source

POJ 2637 WorstWeather Ever

  网上的标程没有一个靠谱的,关于询问超出了所给的年份边界,网上80%的程序都能倍hack掉。

  这道题要注意的是题目卡了int,而且我自身对于lower_bound使用不熟悉。(lower_bound是前闭后开的)

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 51100#define MAXV MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLL#define yes {printf("true\n");continue;}#define no {printf("false\n");continue;}#define maybe {printf("maybe\n");continue;}typedef long long qword;inline int nextInt(){        char ch;        int x=0;        bool flag=false;        do                ch=(char)getchar(),flag=(ch==-)?true:flag;        while(ch<0||ch>9);        do x=x*10+ch-0;        while (ch=(char)getchar(),ch<=9 && ch>=0);        return x*(flag?-1:1);}int n,m;struct aaa{        int y,t;}l[MAXN];bool operator <(aaa a1,aaa a2){        return a1.y<a2.y;}int a[20][MAXN],b[20][MAXN];void init_rmq(){        int i,j;        for (i=0;i<=n;i++)        {                a[0][i]=l[i].t;                b[0][i]=l[i].t;        }        for (j=1;j<20;j++)        {                for (i=0;i+(1<<j)-1<=n;i++)                {                        a[j][i]=min(a[j-1][i],a[j-1][i+(1<<j>>1)]);                        b[j][i]=max(b[j-1][i],b[j-1][i+(1<<j>>1)]);                }        }}int ff[MAXN];int get_max(int l,int r){        if (l>r)return -INF;        return max(b[ff[r-l]][l],b[ff[r-l]][r-(1<<ff[r-l])+1]);}int main(){        freopen("input.txt","r",stdin);        //freopen("output.txt","w",stdout);        int i,j,k;        int x,y,z;        scanf("%d",&n);        memset(ff,-1,sizeof(ff));        for (i=0;i<19;i++)                if ((1<<i)<=n)ff[(1<<i)]=i;        ff[0]=0;        for (i=1;i<=n;i++)        {                if (ff[i]==-1)ff[i]=ff[i-1];        }        for (i=1;i<=n;i++)        {                scanf("%d%d",&l[i].y,&l[i].t);                if (i>1 && l[i].y<l[i-1].y)                        throw 1;        }        l[0].y=-INF;        scanf("%d",&m);        int d1,d2;        aaa t1,t2;        init_rmq();        for (i=0;i<m;i++)        {                scanf("%d%d",&x,&y);    //            if (x>y)no;                t1.y=x;                t2.y=y;                d1=lower_bound(l,l+n+1,t1)-l;                d2=lower_bound(l,l+n+1,t2)-l;                if (l[d2].y==y)//已知今年                {                            if (l[d1].y==x)//已知開始年份                        {                                if (l[d1].t<l[d2].t)no;                                if (get_max(d1+1,d2-1)>=l[d2].t)no;                                if ((qword)d2-d1+1==(qword)y-x+1)yes;                                maybe;//中間年份缺失                        }else                        {                                d1--;                                if (get_max(d1+1,d2-1)>=l[d2].t)no;                                maybe;                        }                }else                {                        if (l[d1].y==x)                        {                                if (l[d1].t<=get_max(d1+1,d2-1))no;                                maybe;                        }else                        {                                maybe;                        }                }        }        return 0;}

 

 

bzoj 1067: [SCOI2007]降雨量 模擬