| Problem Specification | Value |
|---|---|
| Time Limit | 1 Sec |
| Memory Limit | 162 MB |
| Submit | 3535 |
| Solved | 919 |
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 2008Sample Output
false
true
false
maybe
falseHINT
100% 的数据满足: 1<=n<=50000, 1<=m<=10000,-109<=yi<=109, 1<=ri<=10^9
Source
POJ 2637 WorstWeather Ever
一道极其奇怪的特判题...... 一连拍+交了 N 多遍都没有 AC, 但是和 HZW 的代码相比没有 WA.
有什么可说的呢? 自己看代码吧~
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 131100;
class SegmentTree
{
public:
// Segment tree optimized for maximum values' lookup and **not** modification.
// Used for query purposes only.
int n;
int lbnd[maxn], rbnd[maxn];
ll vmx[maxn];
void build_tree(int _n, ll* arr)
{
n = 1; while (n < _n) n *= 2;
for (int i = 1; i <= n; i++) {
lbnd[i + n - 1] = rbnd[i + n - 1] = i;
vmx[i + n - 1] = arr[i];
}
for (int i = n - 1; i >= 1; i--) {
lbnd[i] = lbnd[2 * i];
rbnd[i] = rbnd[2 * i + 1];
vmx[i] = max(vmx[2 * i], vmx[2 * i + 1]);
}
return ;
}
ll query(int p, int l, int r)
{
if (lbnd[p] == l && rbnd[p] == r)
return vmx[p];
if (l >= lbnd[2 * p + 1])
return query(2 * p + 1, l, r);
else if (r <= rbnd[2 * p])
return query(2 * p, l, r);
else
return max(query(2 * p, l, rbnd[2 * p]),
query(2 * p + 1, lbnd[2 * p + 1], r));
}
ll query(int l, int r)
{
if (l > r) return 0;
return query(1, l, r);
}
} st1, st2;
enum determine { True, False, Maybe };
int n, m;
ll arr1[maxn], arr2[maxn], arr3[maxn];
map<ll, int> fnd;
ll my_upper_bound(ll x)
{
if (x < arr1[1])
return 1;
int l = 1, r = n;
while (r > l) {
int m = (l + r) / 2;
if (arr1[m] == x)
return m;
else if (arr1[m] < x)
l = m + 1;
else
r = m;
}
return l;
}
ll my_lower_bound(ll x)
{
if (x > arr1[n])
return n;
int y = my_upper_bound(x);
if (arr1[y] == x)
return y;
else if (arr1[y] > x)
return y - 1;
return 1;
}
determine work(int x, int y)
{
if (x <= y)
return False;
// Those should have never happened...
int x_in, y_in;
ll dis_1, dis_2;
x_in = fnd[x];
y_in = fnd[y]; // If equals to 0 then not in index
if (x_in && y_in) {
// Why would there be such nonsense!
if (x_in - y_in <= 0)
return False;
// There's definitely an answer...
if (x_in - y_in == 1) {
if (x - y > 1) // Lacks adjacency
return arr2[y_in] <= arr2[x_in] ? False : Maybe;
else if (x - y == 1) // Adjacent means permanence
return arr2[y_in] <= arr2[x_in] ? False : True;
else // Doesn't even exists...
return False;
} else if (x_in - y_in > 1) {
if (arr2[y_in] <= arr2[x_in])
return False;
dis_1 = st1.query(y_in + 1, x_in - 1);
dis_2 = st2.query(y_in, x_in - 1);
if (dis_1 > arr2[x_in])
return False;
if (dis_2 > 1)
return Maybe;
return True;
}
}
// If one of them has missing data...
// I'm going to take one of them one at a time, in case I nausea myself
if (x_in && !y_in) {
y_in = my_upper_bound(y);
dis_1 = st1.query(y_in, x_in - 1);
if (dis_1 < arr2[x_in])
return Maybe;
else
return False;
} else if (!x_in && y_in) {
x_in = my_lower_bound(x);
dis_1 = st1.query(y_in + 1, x_in);
if (arr2[y_in] > dis_1)
return Maybe;
else
return False;
}
// Both of them has missing data means we won't be sure of anything.
if (!x_in && !y_in)
return Maybe;
// That's finally final!
return False;
}
int main(int argc, char** argv)
{
scanf("%d", &n);
fnd.clear();
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &arr1[i], &arr2[i]);
fnd[arr1[i]] = i; // Index this year in case of finding things...
if (i >= 2) arr3[i - 1] = arr1[i] - arr1[i - 1];
}
st1.build_tree(n, arr2);
st2.build_tree(n - 1, arr3);
// Typically responding to queries...
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &y, &x); // Guranteed that X > Y
switch (work(x, y)) {
case True:
printf("true\n");
break;
case False:
printf("false\n");
break;
case Maybe:
printf("maybe\n");
break;
default:
break;
}
continue;
}
return 0;
}#include<iostream>
#include<cstdio>
using namespace std;
struct data{int ly,ry,mx,know;}tr[200001];
int n,m;
void build(int k,int l,int r)
{
if(l==r){scanf("%d%d",&tr[k].ly,&tr[k].mx);tr[k].ry=tr[k].ly;tr[k].know=1;return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
tr[k].know=(tr[k<<1].know&&tr[k<<1|1].know);
if(tr[k<<1].ry+1!=tr[k<<1|1].ly)tr[k].know=0;
tr[k].ly=tr[k<<1].ly;tr[k].ry=tr[k<<1|1].ry;
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
int get(int k,int x)
{
if(tr[k].ly==tr[k].ry)
{
if(tr[k].ly!=x)return 0;
else return tr[k].mx;
}
if(x<=tr[k<<1].ry)return get(k<<1,x);
else if(x>=tr[k<<1|1].ly)return get(k<<1|1,x);
return 0;
}
int ask(int k,int x,int y,int num)
{
bool f=0;
if(x<tr[k].ly){f=1;x=tr[k].ly;}
if(tr[k].ly==x&&tr[k].ry==y)
{
if(tr[k].mx>=num)return 0;
else if(tr[k].know&&!f)return 1;
else return 2;
}
if(y<=tr[k<<1].ry)
{
return ask(k<<1,x,y,num);
}
else if(x>=tr[k<<1|1].ly)
{
return ask(k<<1|1,x,y,num);
}
else
{
int t1=ask(k<<1,x,tr[k<<1].ry,num);
int t2=ask(k<<1|1,tr[k<<1|1].ly,y,num);
if(!t1||!t2)return 0;
else if(tr[k<<1].ry+1!=tr[k<<1|1].ly)return 2;
else return 1;
}
}
int getnext(int k,int x)
{
int l=tr[k].ly,r=tr[k].ry;
if(l==r)return tr[k].ly;
if(x<tr[k<<1].ry)return getnext(k<<1,x);
else return getnext(k<<1|1,x);
}
int getlast(int k,int x)
{
int l=tr[k].ly,r=tr[k].ry;
if(l==r)return tr[k].ly;
if(x>tr[k<<1|1].ly)return getlast(k<<1|1,x);
else return getlast(k<<1,x);
}
int main()
{
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
if(r<l){printf("false\n");continue;}
int lnum=get(1,l),rnum=get(1,r);
if(!lnum&&!rnum)printf("maybe\n");
else
{
int s=getnext(1,l),t=getlast(1,r);
if(!lnum)
{
if(s>t||r==t){printf("maybe\n");continue;}
int f=ask(1,s,t,rnum);
if(f==0)printf("false\n");
else printf("maybe\n");
}
else if(!rnum)
{
if(s>t||l==s){printf("maybe\n");continue;}
int f=ask(1,s,t,lnum);
if(f==0)printf("false\n");
else printf("maybe\n");
}
else
{
if(rnum>lnum){printf("false\n");continue;}
if(s>t){
if(l+1==r) printf("true\n");
else printf("maybe\n");
continue;
}
int f=ask(1,s,t,rnum);
if(f==0)printf("false\n");
else if(f==1)
{
if(l+1==s&&r-1==t)printf("true\n");
else printf("maybe\n");
}
else if(ask(1,s,t,rnum)==2)printf("maybe\n");
else printf("false\n");
}
}
}
return 0;
}from pydatagen import *
n = randrange(100, 500)
m = randrange(3000, 10000)
a1 = randlist(n, range(-10**9, 10**9), distinct=True)
a2 = randlist(n, range(1, 10**9))
a1.sort()
printf('%d\n' % n)
for i in range(0, n):
printf('%d %d\n' % (a1[i], a2[i]))
printf('%d\n' % m)
for i in range(0, m):
if possibility(0.6):
b1 = randlist(2, a1, distinct=True)
x = b1[0]
y = b1[1]
if x < y:
x, y = y, x
printf('%d %d\n' % (y, x))
else:
if possibility(0.8):
if possibility(0.5):
x = choice(a1)
y = randrange(min(a1), max(a1) + 1)
if x == y:
y = x - 1
if x < y:
x, y = y, x
printf('%d %d\n' % (y, x))
else:
y = choice(a1)
x = randrange(min(a1), max(a1) + 1)
if x == y:
x = y + 1
if x < y:
x, y = y, x
printf('%d %d\n' % (y, x))
else:
x = randrange(min(a1), max(a1))
y = randrange(min(a1), max(a1))
if x == y:
x = y + 1
if x < y:
x, y = y, x
printf('%d %d\n' % (y, x))
continue