23 条题解
-
1
Sky1231 (sky1231) LV 10 @ 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) return st_ask(lc(now),l,r); else if (st[now].mid+1<=l) return st_ask(rc(now),l,r); else { int lans=st_ask(lc(now),l,st[now].mid); int rans=st_ask(rc(now),st[now].mid+1,r); 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 (task==0) { 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; else if (task==-1) return l; else if (task==1) 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) { int z=st_ask(1,x+1,y); if (a[z].R<a[x].R) printf("maybe\n"); else printf("false\n"); } else if (xv<a[x].Y&&yv==a[y].Y) { int z=st_ask(1,x,y-1); 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) { int z=st_ask(1,x+1,y-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) { int z=st_ask(1,x+1,y-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(); } -
1
-
0
这个代码在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(){ buf[fread(buf,1,MAXSIZE,stdin)]='\0'; bufpos=0; } int readint(){ 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(); int n=readint(); solver.n=n; for(int i=1;i<=n;i++){ a[i]=readint(); b[i]=readint(); solver.update(i,b[i]); } int m=readint(); for(int i=1;i<=m;i++){ int y=readint(),x=readint(); 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); } } -
0
yzl609271536 LV 10 @ 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 -
0
编译通过...
├ 测试数据 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就秒了。 -
0
编译通过...
├ 测试数据 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的情况很特殊。。。。。。就这个问题搞了我好几天
-
0
181818181818 LV 10 @ 2008-01-02 18:13:50
难度为0？？？
-
0
happypumpkin LV 3 @ 2006-10-24 22:22:33
为什么我的河标准答案输出的一样，他还说我错？？？
Sky1231 (sky1231)
LV 10
@ 2020-10-12 19:12:12
