結果

問題 No.461 三角形はいくつ？
コンテスト
ユーザー tubo28
提出日時 2016-12-12 16:00:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,849 bytes
コンパイル時間 1,825 ms
コンパイル使用メモリ 177,580 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-29 16:23:49
合計ジャッジ時間 52,696 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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