結果

問題 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,060 ms
コンパイル使用メモリ 176,476 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 16:54:23
合計ジャッジ時間 51,852 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 7 ms
5,248 KB
testcase_05 AC 1,745 ms
5,248 KB
testcase_06 AC 1,027 ms
5,248 KB
testcase_07 AC 1,185 ms
5,248 KB
testcase_08 AC 811 ms
5,248 KB
testcase_09 AC 5 ms
5,248 KB
testcase_10 AC 256 ms
5,248 KB
testcase_11 AC 1,425 ms
5,248 KB
testcase_12 AC 618 ms
5,248 KB
testcase_13 AC 2,082 ms
5,248 KB
testcase_14 AC 2,133 ms
5,248 KB
testcase_15 AC 2,070 ms
5,248 KB
testcase_16 AC 1,334 ms
5,248 KB
testcase_17 AC 1,322 ms
5,248 KB
testcase_18 AC 2,452 ms
5,248 KB
testcase_19 AC 2,344 ms
5,248 KB
testcase_20 AC 2,024 ms
5,248 KB
testcase_21 AC 2,155 ms
5,248 KB
testcase_22 AC 2,126 ms
5,248 KB
testcase_23 AC 1,043 ms
5,248 KB
testcase_24 AC 981 ms
5,248 KB
testcase_25 AC 7 ms
5,248 KB
testcase_26 AC 7 ms
5,248 KB
testcase_27 TLE -
testcase_28 AC 7 ms
5,248 KB
testcase_29 AC 497 ms
5,248 KB
testcase_30 AC 231 ms
5,248 KB
testcase_31 AC 978 ms
5,248 KB
testcase_32 AC 1,266 ms
5,248 KB
testcase_33 AC 6 ms
5,248 KB
testcase_34 AC 7 ms
5,248 KB
testcase_35 AC 7 ms
5,248 KB
testcase_36 AC 1,099 ms
5,248 KB
testcase_37 AC 1,169 ms
5,248 KB
testcase_38 AC 1,162 ms
5,248 KB
testcase_39 AC 1,213 ms
5,248 KB
testcase_40 AC 1,183 ms
5,248 KB
testcase_41 AC 1,154 ms
5,248 KB
testcase_42 AC 1,432 ms
5,248 KB
testcase_43 AC 1,399 ms
5,248 KB
testcase_44 AC 1,476 ms
5,248 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