結果
問題 | No.743 Segments on a Polygon |
ユーザー |
|
提出日時 | 2018-10-18 23:22:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 1,857 ms |
コンパイル使用メモリ | 202,152 KB |
最終ジャッジ日時 | 2025-01-06 14:33:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename D, D zero>struct Ftree {vector<D> dat;function<D(D, D)> fadd;Ftree(int n, function<D(D, D)> f) : dat(n + 1), fadd(f) {}D operator()(int x) {D s(zero);for (int i = x + 1; i; i -= i & -i) s = fadd(s, dat[i]);return s;}void add(int x, const D &v) {for (int i = x + 1; i < dat.size(); i += i & -i) dat[i] = fadd(dat[i], v);}};vector<int> range_n(int l, int r = -1) { // [l, r), or [0, l) if r == -1vector<int> v;if (~r) v.resize(r - l), iota(v.begin(), v.end(), l);else v.resize(l), iota(v.begin(), v.end(), 0);return v;}signed main() {ios::sync_with_stdio(false);int N, M;cin >> N >> M;vector<int> A(N), B(N);for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];for (int i = 0; i < N; ++i) if (A[i] > B[i]) swap(A[i], B[i]);vector<int> aord(range_n(N));sort(aord.begin(), aord.end(), [&](int i, int j) { return A[i] < A[j]; });int64_t ans = 0;Ftree<int, 0> tree(M, [](int a, int b) { return a + b; });for (int ai = 0; ai < N; ++ai) {int i = aord[ai];ans += tree(B[i] - 1) - tree(A[i]);tree.add(B[i], 1);}cout << ans << endl;return 0;}