Submission #18409

#	Time	Username	Problem	Language	Result	Execution time	Memory
18409		kdh9949	Star triangles (IZhO11_triangle)	C++98	86.36 / 100	2000 ms	5772 KiB

triangle

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Point{
    int x, y;
}p[200010];

int n, x[200010], y[200010], xsum[200010], ysum[200010];
ll ans;

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", x + i, y + i);
        p[i] = {x[i], y[i]};
    }
    sort(x, x + n);
    sort(y, y + n);
    for(int i = 0; i < n; i++){
        p[i] = {(int)(lower_bound(x, x + n, p[i].x) - x), (int)(lower_bound(y, y + n, p[i].y) - y)};
        xsum[p[i].x]++;
        ysum[p[i].y]++;
    }
    for(int i = 0; i < n; i++){
        ans += (ll)(xsum[p[i].x] - 1) * (ll)(ysum[p[i].y] - 1);
    }
    printf("%lld", ans);
}

• Subtask 1: 86.364 / 100