結果

問題 No.461 三角形はいくつ？
ユーザー tubo28tubo28
提出日時 2016-12-12 16:00:51
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,849 bytes
コンパイル時間 1,771 ms
コンパイル使用メモリ 174,304 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-19 20:43:36
合計ジャッジ時間 53,049 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 6 ms
4,380 KB
testcase_05 AC 1,773 ms
4,376 KB
testcase_06 AC 1,044 ms
4,380 KB
testcase_07 AC 1,205 ms
4,376 KB
testcase_08 AC 827 ms
4,376 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 260 ms
4,376 KB
testcase_11 AC 1,449 ms
4,376 KB
testcase_12 AC 629 ms
4,380 KB
testcase_13 AC 2,119 ms
4,376 KB
testcase_14 AC 2,171 ms
4,380 KB
testcase_15 AC 2,104 ms
4,384 KB
testcase_16 AC 1,353 ms
4,376 KB
testcase_17 AC 1,327 ms
4,380 KB
testcase_18 AC 2,495 ms
4,380 KB
testcase_19 AC 2,392 ms
4,380 KB
testcase_20 AC 2,061 ms
4,384 KB
testcase_21 AC 2,192 ms
4,380 KB
testcase_22 AC 2,167 ms
4,380 KB
testcase_23 AC 1,036 ms
4,380 KB
testcase_24 AC 984 ms
4,380 KB
testcase_25 AC 6 ms
4,384 KB
testcase_26 AC 6 ms
4,380 KB
testcase_27 TLE -
testcase_28 AC 6 ms
4,376 KB
testcase_29 AC 505 ms
4,376 KB
testcase_30 AC 234 ms
4,376 KB
testcase_31 AC 994 ms
4,384 KB
testcase_32 AC 1,287 ms
4,380 KB
testcase_33 AC 5 ms
4,376 KB
testcase_34 AC 6 ms
4,376 KB
testcase_35 AC 6 ms
4,380 KB
testcase_36 AC 1,105 ms
4,380 KB
testcase_37 AC 1,173 ms
4,376 KB
testcase_38 AC 1,168 ms
4,376 KB
testcase_39 AC 1,214 ms
4,376 KB
testcase_40 AC 1,188 ms
4,376 KB
testcase_41 AC 1,157 ms
4,376 KB
testcase_42 AC 1,452 ms
4,376 KB
testcase_43 AC 1,423 ms
4,380 KB
testcase_44 AC 1,501 ms
4,376 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;
}
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 < b) && !(b < a);
}
bool operator != (const rational &a, const rational &b) {
  return (a < b) || (b < a);
}

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