Submission #754130

#	Time	Username	Problem	Language	Result	Execution time	Memory
754130		thimote75	Star triangles (IZhO11_triangle)	C++14	100 / 100	418 ms	12472 KiB

triangle

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;

using ipair  = pair<int, int>;
using ipdata = vector<ipair>;

using num = long long;

idata X, Y;
ipdata stars;

int find  (idata &axis, int x) {
    int a = -1;
    int b = axis.size();

    while ( b - a > 1 ) {
        int c = (a + b) >> 1;

        if (axis[c] < x) a = c;
        else b = c;
    }

    return b;
}
int count (idata &axis, int v) {
    int l = find(axis, v);
    int r = find(axis, v + 1);

    return r - l;
}

int main () {
    int N;
    cin >> N;

    for (int i = 0; i < N; i ++) {
        int x, y;
        cin >> x >> y;

        X.push_back(x);
        Y.push_back(y);

        stars.push_back({ x, y });
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    num result = 0;
    for (ipair star : stars) {
        int x = star.first;
        int y = star.second;

        num cx = count(X, x) - 1;
        num cy = count(Y, y) - 1;

        result += cx * cy;
    }

    cout << result << endl;
}

• Subtask 1: 100 / 100