제출 #18421

#제출 시각아이디문제언어결과실행 시간메모리
18421chan492811별들과 삼각형 (IZhO11_triangle)C++98
100 / 100
213 ms8116 KiB
#include <cstdio>
#include <algorithm>
using namespace std;
struct data{
    int x,y,idx;
};
bool compare1(data d1,data d2){
    if(d1.x==d2.x) return d1.y<d2.y;
    return d1.x<d2.x;
}
bool compare2(data d1,data d2){
    if(d1.y==d2.y) return d1.x<d2.x;
    return d1.y<d2.y;
}
int n;
data arr[300010],table[300010];
long long res;
int main(){
    int i,j,k,idx;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d %d",&arr[i].x,&arr[i].y),arr[i].idx=i;
    sort(arr,arr+n,compare1);
    for(i=0;i<n;i=j){
        j=i+1;
        while(j<n && arr[j].x==arr[i].x) j++;
        for(k=i;k<j;k++){
            idx=arr[k].idx; table[idx].y=j-i-1;
        }
    }
    sort(arr,arr+n,compare2);
    for(i=0;i<n;i=j){
        j=i+1;
        while(j<n && arr[j].y==arr[i].y) j++;
        for(k=i;k<j;k++){
            idx=arr[k].idx; table[idx].x=j-i-1;
        }
    }
    for(i=0;i<n;i++){
        res+=table[i].x*table[i].y;
    }
    printf("%lld",res);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...