QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771486 | #7581. Radar Scanner | tarjen# | RE | 0ms | 0kb | C++20 | 2.0kb | 2024-11-22 13:28:25 | 2024-11-22 13:28:25 |
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2>
ostream& operator << (ostream& out,pair<T1,T2> p) {
out<<"("<<p.first<<","<<p.second<<")";
return out;
}
template<typename T>
ostream& operator << (ostream& out,vector<T>v) {
out<<"[";
if(!v.empty()){
cout<<v[0];
for(int i=1;i<v.size();i++)cout<<","<<v[i];
}
out<<"]";
return out;
}
const int N=1005;
int a00[N][N];
int a01[N][N];
int a10[N][N];
int a11[N][N];
void add(int a[][N],int x1,int x2,int y1,int y2){
a[x1][y1]++;
a[x2+1][y1]--;
a[x1][y2+1]--;
a[x2+1][y2+1]++;
};
void all_count(int a[][N]){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++)a[i][j]+=a[i][j-1];
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++)a[i][j]+=a[i-1][j];
}
}
int C3(int n){
if(n<3)return 0;
return n*(n-1)*(n-2)/6;
}
int C2(int n){
if(n<2)return 0;
return n*(n-1)/2;
}
int solve()
{
int n;cin>>n;
memset(a00,0,sizeof(a00));
memset(a01,0,sizeof(a01));
memset(a10,0,sizeof(a10));
memset(a11,0,sizeof(a11));
for(int i=1;i<=n;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if(x1<x2&&y1<y2)add(a00,x1+1,x2,y1+1,y2);
if(x1<x2)add(a10,x1+1,x2,y1,y1);
if(y1<y2)add(a01,x1,x1,y1+1,y2);
add(a11,x1,x1,y1,y1);
}
all_count(a00);
all_count(a01);
all_count(a10);
all_count(a11);
int ans=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
int p00=a00[i][j];
int p01=a01[i][j];
int p10=a10[i][j];
int p11=a11[i][j];
ans+=C3(p11);
ans+=C2(p11)*(p00+p01+p10);
ans+=p11*C2(p00+p01+p10);
ans+=C2(p10)*p01;
ans+=C2(p01)*p10;
ans+=p10*p01*p00;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;while(T--)cout<<solve()<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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