結果
問題 | No.461 三角形はいくつ? |
ユーザー |
![]() |
提出日時 | 2019-02-19 22:20:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 689 ms / 5,000 ms |
コード長 | 1,400 bytes |
コンパイル時間 | 2,189 ms |
コンパイル使用メモリ | 184,928 KB |
実行使用メモリ | 113,608 KB |
最終ジャッジ日時 | 2024-10-12 22:26:03 |
合計ジャッジ時間 | 10,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
コンパイルメッセージ
main.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 23 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h>#include "unistd.h"using namespace std;#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)#define pb push_back#define fi first#define se second#define sz(x) (int)(x).size()#define all(a) (a.begin()),(a.end())typedef __int128_t ll;typedef pair<ll,ll> pll;template<class T>using V=vector<T>;int n;V<pll> v[3], c, s;function<bool (const pll&a, const pll&b)> _less = [](const pll&a, const pll&b){return a.fi*b.se < b.fi*a.se;};pll _plus(const pll&a, const pll&b){return pll(a.fi*b.se+b.fi*a.se, a.se*b.se);};main(){cin.tie(0);ios::sync_with_stdio(false);cin >> n;FOR(i, 0, n){int p, a, b;cin >> p >> a >> b;v[p].pb(pll(a, a+b));}sort(v, v+3, [](const V<pll>&a, const V<pll>&b){return sz(a)<sz(b);});FOR(i, 0, 3){sort(all(v[i]), _less);v[i].pb(pll(1,1));}reverse(all(v[1]));for(pll p0:v[0]) for(pll p1:v[1]){pll p = _plus(p0, p1);if(p.fi < p.se) break;p.fi = p.se*2-p.fi;c.pb(p);p = _less(p0, p1) ? p0 : p1;p.fi = p.se-p.fi;s.pb(p);}sort(all(c), _less);sort(all(s), _less);ll ans = 0;for(pll p:v[2]){ans += distance(s.begin(),upper_bound(all(s), p, _less));ans -= distance(lower_bound(all(c), p, _less),upper_bound(all(c), p, _less));}cout << (long long)ans << endl;}