[Baltic2001]Mars Maps<\/p>\n
Time Limit:5000MS Memory Limit:65536K
Total Submit:19 Accepted:7
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n \u7ed9\u51faN\u4e2a\u77e9\u5f62,N<=10000.\u5176\u5750\u6807\u4e0d\u8d85\u8fc710^9.\u6c42\u5176\u9762\u79ef\u5e76<\/p>\n Input <\/strong><\/p>\n \u5148\u7ed9\u51fa\u4e00\u4e2a\u6570\u5b57N,\u4ee3\u8868\u6709N\u4e2a\u77e9\u5f62. Output <\/strong><\/p>\n \u8f93\u51fa\u9762\u79ef\u5e76<\/p>\n Sample Input <\/strong><\/p>\n 2 Sample Output <\/strong><\/p>\n 225<\/p>\n Source <\/strong><\/p>\n \u8fd9\u662f\u5f88\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u79bb\u6563\u5316\u4e4b\u540e\u7528\u626b\u63cf\u7ebf\u626b\u8fc7\u53bb\uff0c\u7528\u7ebf\u6bb5\u6811\u7ef4\u62a4\u5f53\u524d\u4e0e\u626b\u63cf\u7ebf\u76f8\u4ea4\u7684\u77e9\u5f62\u7684\u957f\u5ea6\u5e76\u3002\u5c31\u53ef\u4ee5\u964d\u7ef4\u4e86\u3002\u3002 [Baltic2001]Mars Maps Time Limit:5000MS Memory Limit:65536KTotal Submit:19 Accepted:7 Case Time Limit:1000MS Description \u7ed9\u51faN\u4e2a\u77e9\u5f62,N<=10000.\u5176\u5750\u6807\u4e0d\u8d85\u8fc710^9.\u6c42\u5176\u9762\u79ef\u5e76 Input \u5148\u7ed9\u51fa\u4e00\u4e2a\u6570\u5b57N,\u4ee3\u8868\u6709N\u4e2a\u77e9\u5f62. \u63a5\u4e0b\u6765N\u884c,\u6bcf\u884c\u56db\u4e2a\u6570,\u4ee3\u8868\u77e9\u5f62\u7684\u5750\u6807. Output \u8f93\u51fa\u9762\u79ef\u5e76 Sample Input 210 10 20 2015 15 25 30 Sample Output 225 Source \u8fd9\u662f\u5f88\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u79bb\u6563\u5316\u4e4b\u540e\u7528\u626b\u63cf\u7ebf\u626b\u8fc7\u53bb\uff0c\u7528\u7ebf\u6bb5\u6811\u7ef4\u62a4\u5f53\u524d\u4e0e\u626b\u63cf\u7ebf\u76f8\u4ea4\u7684\u77e9\u5f62\u7684\u957f\u5ea6\u5e76\u3002\u5c31\u53ef\u4ee5\u964d\u7ef4\u4e86\u3002\u3002\u4e0d\u8fc7\u6211\u60b2\u5267\u4e86\u3002\u6570\u7ec4\u5f00\u5c0f\u4e86\u56e7\u3002\u3002WA\u4e86\u597d\u51e0\u6b21\u3002\u3002Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=10000;int n;int Y[maxn*2];struct Event{ int x,l,r,d; Event(){} Event(int _x,int _l,int _r,int _d):x(_x),l(_l),r(_r),d(_d){} bool operator<(const Event&o)const […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/171"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=171"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/171\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=171"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=171"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=171"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u63a5\u4e0b\u6765N\u884c,\u6bcf\u884c\u56db\u4e2a\u6570,\u4ee3\u8868\u77e9\u5f62\u7684\u5750\u6807.<\/p>\n
10 10 20 20
15 15 25 30<\/p>\n
\u4e0d\u8fc7\u6211\u60b2\u5267\u4e86\u3002\u6570\u7ec4\u5f00\u5c0f\u4e86\u56e7\u3002\u3002WA\u4e86\u597d\u51e0\u6b21\u3002\u3002
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
int n;
int Y[maxn*2];
struct Event
{
int x,l,r,d;
Event(){}
Event(int _x,int _l,int _r,int _d):x(_x),l(_l),r(_r),d(_d){}
bool operator<(const Event&o)const
{
return x<o.x;
}
}E[maxn*2];
void Init()
{
scanf("%d",&n);
int x[2],y[2],cnt=0;
rep(i,n)
{
rep(j,2)scanf("%d %d",x+j,y+j),Y[cnt++]=y[j];
E[2*i]=Event(x[0],y[0],y[1],1);
E[2*i+1]=Event(x[1],y[0],y[1],-1);
}
}
int Cover[8*maxn]={0},Sum[8*maxn]={0};
void change(int t,int l,int r,int a,int b,int d)
{
if(a>=r||b<=l) return;
if(a<=l&&b>=r)Cover[t]+=d;
else change(t*2,l,(l+r)\/2,a,b,d),change(t*2+1,(l+r)\/2,r,a,b,d);
if(Cover[t]>0)
Sum[t]=Y[r]-Y[l];
else
Sum[t]=(l+1==r)?0:(Sum[t*2]+Sum[t*2+1]);
}
void Work()
{
n<<=1;
sort(Y,Y+n);
rep(i,n)
{
E[i].l=lower_bound(Y,Y+n,E[i].l)-Y;
E[i].r=lower_bound(Y,Y+n,E[i].r)-Y;
}
sort(E,E+n);int last=E[0].x;long long Ans=0;
rep(i,n)
{
Event now=E[i];
if(now.x!=last)
{
Ans+=(long long)(Sum[1])*(now.x-last);
last=now.x;
}
change(1,0,n-1,now.l,now.r,now.d);
}
cout<<Ans<<endl;
}
int main()
{
\/\/freopen("in","r",stdin);
Init();
Work();
}<\/p>\n","protected":false},"excerpt":{"rendered":"