Submission #18421

#	Time	Username	Problem	Language	Result	Execution time	Memory
18421		chan492811	Star triangles (IZhO11_triangle)	C++98	100 / 100	213 ms	8116 KiB

triangle

#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;
}

• Subtask 1: 100 / 100