結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-05 21:46:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 3,116 bytes |
コンパイル時間 | 1,305 ms |
コンパイル使用メモリ | 114,204 KB |
実行使用メモリ | 7,460 KB |
最終ジャッジ日時 | 2024-11-14 07:52:47 |
合計ジャッジ時間 | 2,577 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
// includes {{{#include<iostream>#include<iomanip>#include<algorithm>#include<vector>#include<stack>#include<queue>#include<deque>#include<map>#include<set>#include<tuple>#include<cmath>#include<random>#include<cassert>// }}}// #include<bits/stdc++.h>using namespace std;using ll = long long;// NOTE : query in range!/// --- SegmentTree Library {{{ ///template < class Monoid >struct SegTree {private:using T = typename Monoid::T;int n;vector< T > data;// call after touch data[i]void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }public:SegTree() : n(0) {}SegTree(int n, T initial = Monoid::identity()) : n(n) {data.resize(n * 2, initial);for(int i = n - 1; i > 0; i--)data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);}template < class InputIter,class = typename iterator_traits< InputIter >::value_type >SegTree(InputIter first, InputIter last) : SegTree(distance(first, last)) {copy(first, last, begin(data) + n);// fill from deepfor(int i = n - 1; i > 0; i--) prop(i);}void set(int i, const T &v) {data[i += n] = v;while(i >>= 1) prop(i); // propUp}T get(int i) { return data[i + n]; }T query(int l, int r) {T tmpL = Monoid::identity(), tmpR = Monoid::identity();for(l += n, r += n; l < r; l >>= 1, r >>= 1) {if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);if(r & 1) tmpR = Monoid::op(data[--r], tmpR);}return Monoid::op(tmpL, tmpR);}inline void dum(int r = -1) {#ifdef DEBUGif(r < 0) r = n;DEBUG_OUT << "{";for(int i = 0; i < min(r, n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);DEBUG_OUT << "}" << endl;#endif}};/// }}}--- ////// --- Monoid examples {{{ ///struct Nothing {using T = char;using M = char;static constexpr T op(const T &, const T &) { return 0; }static constexpr T identity() { return 0; }template < class X >static constexpr X actInto(const M &, ll, ll, const X &x) {return x;}};struct RangeMin {using T = ll;static T op(const T &a, const T &b) { return min(a, b); }static constexpr T identity() { return numeric_limits< T >::max(); }};struct RangeMax {using T = ll;static T op(const T &a, const T &b) { return max(a, b); }static constexpr T identity() { return numeric_limits< T >::min(); }};struct RangeSum {using T = ll;static T op(const T &a, const T &b) { return a + b; }static constexpr T identity() { return 0; }};/// }}}--- ///using SEG = SegTree< RangeSum >;const int N = 2e5;SEG ecas(N + 1);int main() {std::ios::sync_with_stdio(false), std::cin.tie(0);int n, m;cin >> n >> m;int a, b;vector<pair<int, int>>v;for(int i = 0; i < n; i++) {cin >> a >> b;if(a > b) swap(a, b);v.emplace_back(a, b);}sort((v).begin(), (v).end());ll ans = 0;for(int i = 0; i < n; i++) {int a, b;tie(a, b) = v[i];ans += ecas.query(a, b);ecas.set(b, 1);}cout << ans << endl;return 0;}