Educational Codeforces Round 113

ganking / 2023-09-02 / 原文

稳定发挥4题
A题文件输出没去掉WA了一发
B题特殊情况没判到，WA了好几发，中间还交到D题去了
C题简单判断一下无解，然后组合数求一下就行
D题其实也挺简单的，考虑严格夹在两条竖线之间的点（不包括边界），如果它们不是在同一水平线上，则必然大于Manhattan距离，而且两个点对之间要么是x方向走多了，要么是y方向走多了，不会出现重叠的情况，扫两遍即可。

怎么cf这么喜欢卡unorder_map，两天都是这样
换成map就A了

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<iostream>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef double db;
typedef long long ll; //
const int N=1e6+5;
const ll mo=998244353;
struct node{
	int x,y,op;
};
node a[N];
int x[N],y[N],n,m,k,xx[N],yy[N],tot;
map<int,int> f;
ll ans;
bool cmp(node a,node b){
	if (a.x!=b.x) return a.x<b.x;
	return a.op<b.op;
}
void solve(){
	ll s=0;
	int bo=0;
	f.clear();
	
	fo(i,1,tot) {
		if (a[i].op==1) {
			bo=a[i].x;
			f.clear();
			s=0;
		}
		else{
			if (a[i].x==bo) continue;
			ans+=s;
			if (f.find(a[i].y)!=f.end()) ans-=(ll)f[a[i].y];
			f[a[i].y]++;
			s++;
		}
	}
}
int main() {
	
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);

	
	int T;
	scanf("%d",&T);
	while (T--){
		ans=0;

		scanf("%d %d %d",&n,&m,&k);
		fo(i,1,n) scanf("%d",&x[i]);
		fo(i,1,m) scanf("%d",&y[i]);
		
		fo(i,1,k) {
			scanf("%d %d",&xx[i],&yy[i]);
		}
		
		tot=0;
		fo(i,1,n) a[++tot]=(node){x[i],0,1};
		fo(i,1,k) a[++tot]=(node){xx[i],yy[i],2};
		sort(a+1,a+tot+1,cmp);
		
		solve();
		
		tot=0;
		fo(i,1,m) a[++tot]=(node){y[i],0,1};
		fo(i,1,k) a[++tot]=(node){yy[i],xx[i],2};
		sort(a+1,a+tot+1,cmp);
	
		solve();
		
		printf("%lld\n",ans);


	}
	return 0;
}