QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771489 | #7581. Radar Scanner | tarjen# | WA | 163ms | 19428kb | C++20 | 2.0kb | 2024-11-22 13:31:17 | 2024-11-22 13:31:18 |
Judging History
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;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 19420kb
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
output:
0 4
result:
ok 2 number(s): "0 4"
Test #2:
score: -100
Wrong Answer
time: 163ms
memory: 19428kb
input:
10 5 2 1 3 3 1 5 1 5 1 2 2 3 4 1 5 3 1 2 4 4 10 3 3 7 5 3 4 3 4 5 4 6 6 8 1 10 6 6 1 9 8 2 6 8 10 3 2 8 7 5 1 5 8 2 2 7 7 1 1 2 3 100 1 37 28 37 1 5 6 40 9 29 47 30 12 9 12 9 40 14 45 14 13 28 16 34 44 8 46 47 23 9 40 42 13 1 35 17 9 31 46 31 1 10 34 48 5 35 46 50 16 21 28 49 3 6 3 24 5 3 39 28 30 8...
output:
1 31 16256 1725574645 1446359451 -1643601419 -2121589113 -258663853 -1556253900 717269638
result:
wrong answer 4th numbers differ - expected: '29932636832595', found: '1725574645'