(未完待续)
题目链接:GMOJ 6297/九校联考 2018 D2T3。
题目
题目描述
输入格式
输出格式
样例输入输出
数据范围
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
GMOJ 6297 | $2\text{s}$ | $128\text{MiB}$ |
题解
先放一下代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
using std::pair;
using std::make_pair;
using std::sort;
using std::lower_bound;
#include<vector>
using std::vector;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
register char ch=getchar();
register int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=100000+5;
struct Node{
ll x,y;
int val;
inline Node(void){
return;
}
inline Node(ll a,ll b,int c){
x=a,y=b,val=c;
return;
}
inline bool operator<(const Node &a)const{
return x<a.x;
}
};
struct TreeArray{
int n,unit[MAXN*3];
#define lowbit(x) ( (x) & ( - (x) ) )
inline void Init(int num){
n=num;
memset(unit,0,sizeof(unit));
return;
}
inline void Update(int ID,int val){
while(ID<=n){
unit[ID]+=val;
ID+=lowbit(ID);
}
return;
}
inline int Query(int ID){
register int sum=0;
while(ID){
sum+=unit[ID];
ID-=lowbit(ID);
}
return sum;
}
};
int n,m,D;
int covered[MAXN];
ll Min,Max,Another;//Min,Max是加的总和,Another是减的总和
TreeArray T;
pair<ll,ll> W[MAXN],B[MAXN];
vector<Node> E;//扫描线事件
vector<ll> Listx,Listy;//x离散化列表,y离散化列表
inline int GetID_of_y(ll);
inline void Solve(int,int,pair<ll,ll>[],pair<ll,ll>[]);
int main(void){
freopen("mhw.in","r",stdin);
freopen("mhw.out","w",stdout);
register int i;
n=read(),m=read(),D=read();
//scanf("%d%d%d",&n,&m,&D);
for(i=1;i<=n;++i){
static int x,y;
x=read(),y=read();
//scanf("%d%d",&x,&y);
W[i]=make_pair(x+y,x-y);
}
for(i=1;i<=m;++i){
static int x,y;
x=read(),y=read();
//scanf("%d%d",&x,&y);
B[i]=make_pair(x+y,x-y);
}
sort(W+1,W+n+1);
sort(B+1,B+m+1);//排序
Solve(n,m,W,B);//第一次
Solve(m,n,B,W);//交换参数,重做
printf("%lld %lld\n",Min-Another,Max-Another);
fclose(stdin);
fclose(stdout);
return 0;
}
inline int GetID_of_y(ll n){//离散化后查询序号
return lower_bound(Listy.begin(),Listy.end(),n)-Listy.begin()+1;
}
inline void Solve(int n,int m,pair<ll,ll>W[],pair<ll,ll>B[]){
register int i,j,k;
E.clear();
Listx.clear();
Listy.clear();
for(i=1;i<=m;++i){
E.push_back(Node(B[i].first-D,B[i].second,1));
E.push_back(Node(B[i].first+D+1,B[i].second,-1));
Listx.push_back(B[i].first-D);
Listx.push_back(B[i].first+D+1);
Listy.push_back(B[i].second);
}
for(i=1;i<=n;++i){
Listx.push_back(W[i].first);
Listy.push_back(W[i].second-D-1);
Listy.push_back(W[i].second+D);
}
sort(E.begin(),E.end());
sort(Listx.begin(),Listx.end());
sort(Listy.begin(),Listy.end());
Listx.erase(unique(Listx.begin(),Listx.end()),Listx.end());
Listy.erase(unique(Listy.begin(),Listy.end()),Listy.end());
T.Init(Listy.size());
for(i=j=0,k=1;i<(int)Listx.size();++i){
ll x=Listx[i];
while(j<(int)E.size()&&E[j].x==x){//更新
T.Update(GetID_of_y(E[j].y),E[j].val);
++j;
}
while(k<=n&&W[k].first==x){//统计答案
covered[k]=T.Query(GetID_of_y(W[k].second+D))-T.Query(GetID_of_y(W[k].second-D-1));//询问离散化的纵坐标的区间和
++k;
}
}
sort(covered+1,covered+n+1);
for(i=1;i<=n;++i){
Min+=(ll)(n-i)*covered[i];//n-i个比它大
Max+=(ll)(n-i)*covered[n-i+1];//n-i个比它小
Another+=(ll)covered[i]*(covered[i]-1)>>1;//加到减的总和里面
}
return;
}
你才高一?????