結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2019-04-24 22:48:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 4,327 bytes |
コンパイル時間 | 2,318 ms |
コンパイル使用メモリ | 182,196 KB |
実行使用メモリ | 9,120 KB |
最終ジャッジ日時 | 2024-11-15 17:55:06 |
合計ジャッジ時間 | 5,180 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#define _USE_MATH_DEFINES#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>using namespace std;/*BigInteger#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#include <boost/rational.hpp>namespace xxx = boost::multiprecision;using Bint = xxx::cpp_int;using Real = xxx::number<xxx::cpp_dec_float<1024>>;*/#define int long long#define pb(x) push_back(x)#define m0(x) memset((x), 0, sizeof(x))#define mm(x) memset((x), -1, sizeof(x))//container#define ALL(x) (x).begin(), (x).end()#define RALL(a) (a).rbegin(), (a).rend()#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)#define EXIST(s, e) ((s).find(e) != (s).end())#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());#define PERM(c) \sort(ALL(c)); \for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))// debug#define GET_VAR_NAME(variable) #variable#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;// bit_macro#define bit(n) (1LL << (n))#define bitset(a, b) (a) |= (1 << (b))#define bitunset(a, b) (a) &= ~(1 << (b))#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)#define bitcount(a) __builtin_popcountll((a))//typedeftypedef long long lint;typedef unsigned long long ull;typedef complex<long double> Complex;typedef pair<int, int> P;typedef tuple<int, int, int> TP;typedef vector<int> vec;typedef vector<vec> mat;//constantconstexpr int INF = (int)1e18;constexpr int MOD = (int)1e9 + 7;constexpr double PI = (double)acos(-1);constexpr double EPS = (double)1e-10;constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};//template <typename T>void chmax(T &a, T b) { a = max(a, b); }template <typename T>void chmin(T &a, T b) { a = min(a, b); }//inline int toInt(string s) {int v;istringstream sin(s);sin >> v;return v;}template <class T>inline string toString(T x) {ostringstream sout;sout << x;return sout.str();}//struct Accelerate_Cin {Accelerate_Cin() {cin.tie(0);ios::sync_with_stdio(0);cout << fixed << setprecision(20);};};//一点更新区間所得//初期化:O(N)//一点更新:O(log N)//区間所得:O(log N)//T:要素の型 E:作用素の型//n:要素数 dat:要素の配列//n_:配列のサイズ f:要素と要素をマージする関数 g:要素に作用させる関数 d1:要素の単位元 v:初期配列//ex) RMQ: f(a,b)=min(a,b) g(dat[k],a)=(dat[k]=a) d1:INFtemplate <typename T, typename E>struct SegmentTree {using F = function<T(T, T)>;using G = function<T(T, E)>;int n;F f;G g;T d1;vector<T> dat;SegmentTree(int n_, F f, G g, T d1, vector<T> v = vector<T>()) {this->f = f, this->g = g, this->d1 = d1;init(n_);if (n_ == (int)v.size()) build(n_, v);}void init(int n_) {n = 1;while (n < n_) n *= 2;dat.clear();dat.resize(2 * n - 1, d1);}void build(int n_, vector<T> v) {for (int i = 0; i < n_; i++) dat[i + n - 1] = v[i];for (int i = n - 2; i >= 0; i--) f(dat[2 * i + 1], dat[2 * i + 2]);}void update(int k, E a) {k += n - 1;dat[k] = g(dat[k], a);while (k > 0) {k = (k - 1) / 2;dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);}}T query(int a, int b, int k, int l, int r) {if (r <= a || b <= l) return d1;if (a <= l && r <= b) return dat[k];T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);return f(vl, vr);}T query(int a, int b) {return query(a, b, 0, 0, n);}};int N, M;vector<P> v;signed main() {cin >> N >> M;for (int i = 0; i < N; i++) {int a, b;cin >> a >> b;if (a > b) swap(a, b);v.push_back(P(a, b));}sort(ALL(v));SegmentTree<int, int> seg(202020,[&](int a, int b) {return a + b;},[&](int a, int b) {return a + b;},0);int ans = 0;for (auto x : v) {ans += seg.query(x.first, x.second);seg.update(x.second, 1);}cout << ans << endl;return 0;}/*3 7 0 1 2 4 3 6*/