栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3042 City Selection II

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3042 City Selection II

#include <string.h>#include <stdio.h>#include <iostream>#include <algorithm>using namespace std;#define maxn 200009int g[maxn*2],ans;struct node{int l,r,addv,sum;}a[maxn*2*3];int n,m;void init(int g[],int &ans){if(ans==0)return;sort(g+1,g+1+ans);int m=ans;ans=1;for(int i=2;i<=m;i++)if(g[i]!=g[ans])g[++ans]=g[i];}int find(int v){int lf=1,rt=ans,mid;while(1){mid=(lf+rt)/2;if(g[mid]<v)lf=mid+1;else if(g[mid]>v)rt=mid-1;elsereturn mid;}}struct pt{int x,y,col;}b[maxn],res[maxn];bool operator <(const pt &elem1,const pt &elem2){if(elem1.y-elem1.x==elem2.y-elem2.x)return elem1.col<elem2.col;return elem1.y-elem1.x>elem2.y-elem2.x;}bool cmp(const pt &elem1,const pt &elem2){if(elem1.x==elem2.x)return elem1.y<elem2.y;return elem1.x<elem2.x;}void create(int p,int lf,int rt){a[p].l=lf;a[p].r=rt;a[p].addv=a[p].sum=0;if(lf==rt)return;int mid=(a[p].l+a[p].r)/2;create(p*2,lf,mid);create(p*2+1,mid+1,rt);}void insert(int p,int lf,int rt){if(a[p].l==lf&&a[p].r==rt){a[p].addv++;a[p].sum+=(rt-lf+1);return;}int mid=(a[p].l+a[p].r)/2;if(a[p].addv){a[p*2].addv+=a[p].addv;a[p*2].sum+=a[p].addv*(a[p*2].r-a[p*2].l+1);a[p*2+1].addv+=a[p].addv;a[p*2+1].sum+=a[p].addv*(a[p*2+1].r-a[p*2+1].l+1);a[p].addv=0;}if(rt<=mid)insert(p*2,lf,rt);else if(lf>mid)insert(p*2+1,lf,rt);else{insert(p*2,lf,mid);insert(p*2+1,mid+1,rt);}a[p].sum=a[p*2].sum+a[p*2+1].sum;}int find(int p,int lf,int rt){if(a[p].l==lf&&a[p].r==rt)return a[p].sum;if(a[p].addv)return a[p].addv;if(a[p].sum==0)return 0;int mid=(a[p].l+a[p].r)/2;if(rt<=mid)return find(p*2,lf,rt);else if(lf>mid)return find(p*2+1,lf,rt);elsereturn find(p*2,lf,mid)+find(p*2+1,mid+1,rt);}void solve(){create(1,1,ans);sort(b+1,b+1+n+m);int K=0,x,y,lf,rt;for(int i=1;i<=n+m;i++){x=b[i].x;y=b[i].y;lf=find(y+2*x);rt=find(y+2*x+3);if(b[i].col==0)insert(1,lf,rt-1);else{if(find(1,lf,rt-1)==0)res[++K]=b[i];}}printf("%dn",K);sort(res+1,res+1+K,cmp);for(int i=1;i<=K;i++)printf("(%d,%d)n",res[i].x,res[i].y);}int main(){for(;;){if(scanf("%d%d",&n,&m)==EOF)break;ans=0;for(int i=1;i<=n+m;i++){scanf("%d%d",&b[i].x,&b[i].y);if(i<=n)b[i].col=0;elseb[i].col=1;g[++ans]=b[i].y+2*b[i].x;g[++ans]=b[i].y+2*b[i].x+3;}init(g,ans);solve();}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/377158.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号