結果

問題 No.461 三角形はいくつ？
ユーザー tubo28tubo28
提出日時 2016-12-12 17:34:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,318 bytes
コンパイル時間 2,097 ms
コンパイル使用メモリ 177,764 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-05-07 04:09:37
合計ジャッジ時間 52,566 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 7 ms
6,944 KB
testcase_05 AC 1,750 ms
6,940 KB
testcase_06 AC 1,030 ms
6,944 KB
testcase_07 AC 1,188 ms
6,940 KB
testcase_08 AC 817 ms
6,944 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 256 ms
6,940 KB
testcase_11 AC 1,426 ms
6,944 KB
testcase_12 AC 620 ms
6,944 KB
testcase_13 AC 2,086 ms
6,940 KB
testcase_14 AC 2,138 ms
6,940 KB
testcase_15 AC 2,077 ms
6,940 KB
testcase_16 AC 1,342 ms
6,940 KB
testcase_17 AC 1,324 ms
6,940 KB
testcase_18 AC 2,458 ms
6,944 KB
testcase_19 AC 2,349 ms
6,944 KB
testcase_20 AC 2,026 ms
6,944 KB
testcase_21 AC 2,155 ms
6,944 KB
testcase_22 AC 2,132 ms
6,944 KB
testcase_23 AC 1,034 ms
6,944 KB
testcase_24 AC 981 ms
6,940 KB
testcase_25 AC 6 ms
6,940 KB
testcase_26 AC 7 ms
6,944 KB
testcase_27 TLE -
testcase_28 AC 6 ms
6,940 KB
testcase_29 AC 496 ms
6,944 KB
testcase_30 AC 230 ms
6,940 KB
testcase_31 AC 980 ms
6,940 KB
testcase_32 AC 1,268 ms
6,940 KB
testcase_33 AC 6 ms
6,944 KB
testcase_34 AC 6 ms
6,944 KB
testcase_35 AC 7 ms
6,944 KB
testcase_36 AC 1,102 ms
6,944 KB
testcase_37 AC 1,169 ms
6,944 KB
testcase_38 AC 1,161 ms
6,940 KB
testcase_39 AC 1,214 ms
6,944 KB
testcase_40 AC 1,185 ms
6,940 KB
testcase_41 AC 1,151 ms
6,948 KB
testcase_42 AC 1,433 ms
6,944 KB
testcase_43 AC 1,401 ms
6,944 KB
testcase_44 AC 1,477 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

typedef long long Integer;
Integer gcd(Integer a, Integer b) { return a > 0 ? gcd(b % a, a) : b; }
struct rational {
    Integer p, q;
    void normalize() { // keep q positive
        if (q < 0) p *= -1, q *= -1;
        Integer d = gcd(p < 0 ? -p : p, q);
        if (d == 0) p = 0, q = 1;
        else        p /= d, q /= d;
    }
    rational(Integer p, Integer q = 1) : p(p), q(q) {
        normalize();
    }
    rational &operator += (const rational &a) {
        p = a.q * p + a.p * q; q = a.q * q; normalize();
        return *this;
    }
    rational &operator -= (const rational &a) {
        p = a.q * p - a.p * q; q = a.q * q; normalize();
        return *this;
    }
    rational &operator *= (const rational &a) {
        p *= a.p; q *= a.q; normalize();
        return *this;
    }
    rational &operator /= (const rational &a) {
        p *= a.q; q *= a.p; normalize();
        return *this;
    }
    rational &operator - () {
        p *= -1;
        return *this;
    }
};
rational operator + (const rational &a, const rational &b) {
    return rational(a) += b;
}
rational operator * (const rational &a, const rational &b) {
    return rational(a) *= b;
}
rational operator - (const rational &a, const rational &b) {
    return rational(a) -= b;
}
rational operator / (const rational &a, const rational &b) {
    return rational(a) /= b;
}
bool operator < (const rational &a, const rational &b) { // avoid overflow
    // return (long double)a.p * b.q < (long double)a.q * b.p;
    return a.p * b.q < a.q * b.p;
}
bool operator <= (const rational &a, const rational &b) {
    return !(b < a);
}
bool operator > (const rational &a, const rational &b) {
    return b < a;
}
bool operator >= (const rational &a, const rational &b) {
    return !(a < b);
}
bool operator == (const rational &a, const rational &b) {
    return a.p == b.p && a.q == b.q;
}
bool operator != (const rational &a, const rational &b) {
    return !(a == b);
}

int n;
vector<rational> ls[3];

int main() {
    while (cin >> n) {
        for (int i = 0; i < 3; ++i) ls[i].clear();
        rep(i, n) {
            int p;
            int a, b;
            cin >> p >> a >> b;
            ls[p].emplace_back(a, a + b);
        }
        for (int i = 0; i < 3; ++i) sort(all(ls[i]));

        // 1本
        ll ans = n + 1;

        for (auto &x : ls[1]) {
            x = 1 - x;
            ans += ls[0].end() - upper_bound(all(ls[0]), x);
        }
        for (auto &y : ls[2]) {
            y = 1 - y;
            ans += ls[0].end() - upper_bound(all(ls[0]), y);
        }

        for (auto &x : ls[1]) {
            for (auto &y : ls[2]) {
                if (x + y < 1) {
                    // 2本 (1,2)
                    ++ans;
                }
                if (x + y <= 1) {
                    // 3本 (0,1,2)
                    int a = lower_bound(all(ls[0]), x + y) - lower_bound(all(ls[0]), max(x, y));
                    int b = ls[0].end() - upper_bound(all(ls[0]), x + y);
                    ans += a + b;
                }
            }
        }
        cout << ans << endl;
    }
}
0