当前位置:网站首页>B - Code Party (girls' competition)
B - Code Party (girls' competition)
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】
B - Code Party
Sample Input
2
3
3 1 3 1
1 1 2 3
2 1 3 2
5
1 1 4 5
2 1 3 2
2 2 3 3
4 5 4 5
1 2 2 4
Sample Output
0
4
// Now it's time ,2021 year 10 month 28 Number 00:38 I finally ac 了 ,,,, Woo woo
/* Their thinking Using the difference and two-dimensional prefix sum, the number of intervals covered on each lattice is calculated g[i][j]. If you ask at this time C(g[i][j],3) And , Then there will be a lot of repetition , Because the same three intervals can cover multiple grids . So we only keep the grid in the upper left corner of the coverage area , Because this grid must be on the top and left of the interval , So the final answer is : The sum of the - Delete the sum after the left - Delete the sum after the top + Delete the sum after the top and left ( This piece has been repeatedly reduced in the front , So add it back ). */
#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#define N 1005
using namespace std;
typedef long long ll;
int a1[N][N],a2[N][N],a3[N][N],a4[N][N];
ll c3[100005];
ll wo(int a[N][N])
{
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];// Sum up ;
}
}
ll ans=0;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
ans+=c3[a[i][j]]; // altogether ( Buckle ) Overlapping ans;
}
}
return ans;
}
int main(){
int T;
c3[3]=1;
cin>>T;
for(int i=4;i<=100000;i++){
c3[i]=(ll)i*(i-1)*(i-2)/6;// If there is i The situation of the same Geke team
}
while(T--)
{
int n;
cin>>n;
memset(a1,0,sizeof(a1));// Each cycle assignment 0;
memset(a2,0,sizeof(a2));
memset(a3,0,sizeof(a3));
memset(a4,0,sizeof(a4));
int x1,y1,x2,y2;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);// It works cin It's over time , There will be no competition in the future cin;
a1[x1][y1]++,a1[x2+1][y1]--,a1[x1][y2+1]--,a1[x2+1][y2+1]++;
// Two dimensional difference , Give (x1,y1) To (x2,y2) Add 1;
a2[x1+1][y1]++,a2[x2+1][y1]--,a2[x1+1][y2+1]--,a2[x2+1][y2+1]++;
// Subtract the left from each matrix ( Except for the first line ),x1+1;
a3[x1][y1+1]++,a3[x2+1][y1+1]--,a3[x1][y2+1]--,a3[x2+1][y2+1]++;
// Subtract the upper edge from each matrix ( Except for the first column ),y1+1;
a4[x1+1][y1+1]++,a4[x2+1][y1+1]--,a4[x1+1][y2+1]--,a4[x2+1][y2+1]++;
// Plus plus minus ;
}
cout<<wo(a1)-wo(a2)-wo(a3)+wo(a4)<<endl;
}
return 0;
}
边栏推荐
- mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
- [exercise-3] (UVA 442) matrix chain multiplication
- 0-1 knapsack problem (I)
- 渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
- C语言必背代码大全
- Penetration test (3) -- Metasploit framework (MSF)
- 快速转 TypeScript 指南
- Accounting regulations and professional ethics [1]
- Alice and Bob (2021牛客暑期多校训练营1)
- New to redis
猜你喜欢
随机推荐
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
Research Report on market supply and demand and strategy of Chinese graphic screen printing equipment industry
0-1背包問題(一)
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
Accounting regulations and professional ethics [3]
数据在内存中的存储&载入内存,让程序运行起来
C语言学习笔记
Frida hook so layer, protobuf data analysis
China's salt water membrane market trend report, technological innovation and market forecast
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Accounting regulations and professional ethics [1]
Determine the Photo Position
F - Birthday Cake(山东省赛)
Research Report on market supply and demand and strategy of geosynthetics industry in China
nodejs爬虫
Nodejs crawler
Accounting regulations and professional ethics [5]
B - 代码派对(女生赛)
Shell脚本编程
Web based photo digital printing website