# 23 条题解

• @ 2020-10-12 19:12:12
``````#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
struct inf
{
int Y,R;
};

int cmp_inf(inf a,inf b)
{
return a.Y<b.Y;
}

struct node
{
int l,r,mid,num;
};

int n,m;
inf a[50000+1];
node st[(50000<<2)+2];

#define lc(now) ((now)<<1)
#define rc(now) ((now)<<1|1)

void st_build(int now,int l,int r)
{
st[now].l=l,st[now].r=r;
if (l<r)
{
st[now].mid=(l+r)>>1;
st_build(lc(now),l,st[now].mid);
st_build(rc(now),st[now].mid+1,r);
if (a[st[lc(now)].num].R>=a[st[rc(now)].num].R)
st[now].num=st[lc(now)].num;
else
st[now].num=st[rc(now)].num;
}
else if (l==r)
st[now].num=l;
}

int st_ask(int now,int l,int r)
{
if (st[now].l==l&&r==st[now].r)
return st[now].num;
else if (r<=st[now].mid)
else if (st[now].mid+1<=l)
else
{
if (a[lans].R>=a[rans].R)
return lans;
else
return rans;
}
}

int search(int Y,int task=0)
{
int l,r,mid;
for (l=1,r=n;r-l>1;)
{
mid=(l+r)>>1;
if (Y<a[mid].Y)
r=mid;
else if (Y>a[mid].Y)
l=mid;
else
return mid;
}
{
if (Y==a[l].Y)
return l;
else if (Y==a[r].Y)
return r;
else
return 0;
}
else if (Y<a[l].Y)
return l;
else if (Y>a[r].Y)
return r;
return l;
return r;
}

void main()
{
while (~scanf("%d",&n))
{
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].Y,&a[i].R);
sort(&a[1],&a[n+1],cmp_inf);
st_build(1,1,n);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int xv,yv;
scanf("%d%d",&xv,&yv);
int x=search(xv),y=search(yv);
if (x==0||y==0||y-x<yv-xv)
{
//沒有足夠的數據
if (x==0)
x=search(xv,1);
if (y==0)
y=search(yv,-1);
if ((xv<a[x].Y&&a[y].Y<yv)||x==y)
printf("maybe\n");
else if (xv==a[x].Y&&a[y].Y<yv)
{
if (a[z].R<a[x].R)
printf("maybe\n");
else
printf("false\n");
}
else if (xv<a[x].Y&&yv==a[y].Y)
{
if (a[z].R<a[y].R)
printf("maybe\n");
else
printf("false\n");
}
else if (xv==a[x].Y&&yv==a[y].Y)
{
if (y-x>1)
{
if (a[z].R<a[y].R&&a[y].R<=a[x].R)
printf("maybe\n");
else
printf("false\n");
}
else
{
if (a[y].R<=a[x].R)
printf("maybe\n");
else
printf("false\n");
}
}
}
else if (y-x>1)
{
if (a[z].R<a[y].R&&a[y].R<=a[x].R)
printf("true\n");
else
printf("false\n");
}
else
{
if (a[y].R<=a[x].R)
printf("true\n");
else
printf("false\n");
}
}
}
}
}

int main()
{
dts::main();
}
``````
• @ 2017-02-02 09:56:54

mdzz线段树60

• @ 2017-08-06 17:48:08

+1
和降雨量的数据有什么区别？

• @ 2017-09-11 12:30:03

这个代码在bzoj和Vijos上都能A,给各位做参考QAQ

``````#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cassert>
using namespace std;
#define fi first
#define sc second
#define show(x) printf("%s=%d\n",#x,x);
typedef pair<int*,int*> pip;
typedef int ll;
const int MAXSIZE=10000020;
const int INF=0x3f3f3f3f;
const int maxn=50001;
int bufpos;
char buf[MAXSIZE];
void init(){
bufpos=0;
}
bool isneg;
int val=0;
for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
for(;isdigit(buf[bufpos]);bufpos++)
val=val*10+buf[bufpos]-'0';
return isneg?-val:val;
}
struct segtree{
ll maxv[maxn*8];
int n,p;
ll v;
segtree(){
memset(maxv,0,sizeof(maxv));
}
void _update_(int o,int l,int r){
if (l==r){
maxv[o]=v;
assert(l==p);
return;
}
ll m=l+(r-l)/2;
//puts("line 35");
if (p<=m)
_update_(o*2,l,m);
else _update_(o*2+1,m+1,r);
maxv[o]=max(maxv[o*2],maxv[o*2+1]);
}
void update(int p,ll v){
this->p=p;
this->v=v;
_update_(1,1,n);
//puts("updated once");
}
int ql,qr;
ll _query_(int o,int l,int r){
if (ql<=l && r<=qr)
return maxv[o];
ll ans=-INF;
int m=l+(r-l)/2;
if (ql<=m)
ans=max(ans,_query_(o*2,l,m));
if (qr>=m+1)
ans=max(ans,_query_(o*2+1,m+1,r));
return ans;
}
ll query(int l,int r){
if (l>r)
return -INF;
l=max(l,1);
r=min(r,n);
ql=l;
qr=r;
return _query_(1,1,n);
}
};
segtree solver;
int a[maxn],b[maxn];
int main(){
init();
solver.n=n;
for(int i=1;i<=n;i++){
solver.update(i,b[i]);
}
for(int i=1;i<=m;i++){
pip px=equal_range(a+1,a+n+1,x),py=equal_range(a+1,a+n+1,y);
bool xknown=px.fi!=px.sc,yknown=py.fi!=py.sc,oknown=xknown && yknown && py.fi-px.fi==*py.fi-*px.fi;
int mmax=solver.query(py.sc-a,px.fi-a-1);
//show(mmax);show(xknown);show(yknown);show(oknown);show(py.sc-a);show(px.fi-a-1);
if (oknown && mmax<b[px.fi-a] && b[px.fi-a]<=b[py.fi-a]){
puts("true");
continue;
}
if (xknown && yknown){
if (mmax<b[px.fi-a] && b[px.fi-a]<=b[py.fi-a])
puts("maybe");
else puts("false");
continue;
}
if (!yknown || !xknown){
if ((!yknown && !xknown) || (xknown && mmax<b[px.fi-a]) || (yknown && mmax<b[py.fi-a]))
puts("maybe");
else puts("false");
continue;
}
assert(false);
}
}
``````
• @ 2009-10-23 10:01:42

注意这样的数据

4

1 10

2 11

4 5

5 6

2

1 5

2 5

输出：

false

maybe

~~~~~~~~~~~~~~~~~~~~~~无奈的分割线~~~~~~~~~~~~~~~~~~~~~~~~~

就因为这个提交了好几次。。

还有输出用write吧

• @ 2009-10-20 15:30:45

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：300ms

离散化线段树

Orz mike_nzk的1.83K程序

我的沙茶程序4.77K

• @ 2009-10-10 19:59:10

题解：

PS:程序还好，75行，1.83KB，并且用writeln秒杀了此题。

• @ 2009-07-28 15:11:30

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：306ms

离散化OK。。。

据说把writeln改为write就秒了。

• @ 2009-04-17 21:15:58

这体牛B

• @ 2009-02-21 20:26:22

知道了……

原来难度为00=无穷大……

• @ 2008-10-26 18:15:20

x=y 的时候应该怎么做啊

谁能把程序发一下 我做不出来 啊

• @ 2008-10-01 11:30:04

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我真的很鄙视这个数据，x=y的情况很特殊。。。。。。就这个问题搞了我好几天

• @ 2008-01-02 18:13:50

难度为0？？？

• @ 2007-11-10 18:44:41

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 88ms

• @ 2007-10-19 19:15:09

线段树就可以了啊。。。

似乎不是很难。。

• @ 2007-08-22 23:06:09

才30分。。。大牛快来解释阿！！！怎么做。。。

• @ 2006-10-24 22:22:33

为什么我的河标准答案输出的一样，他还说我错？？？

• @ 2006-10-24 22:20:50

原来有这种错误。。

当X=Y的时候。。

“·X年和Y年以及这两年间的任意年份的降雨量都是已知的。”

这是个很重要的条件。。

如果已知就输出true否则maybe。。

虽然可以确定。。如果X=Y那么显然符合条件。。但是。。

唉……不说什么了。。

• @ 2006-10-17 18:33:36

用树做的 考试的时候只得了30分 郁闷 调了接近半个小时

有谁能明确说一下到低"true""false""maybe"该如何判定啊

• @ 2006-10-16 19:12:01

我怎么搞都只过一个点

• @ 2006-10-16 18:59:22

道歉，这是我的问题，请管理员改一下吧

ID
1265

8

426

33

8%

1