結果
問題 | No.743 Segments on a Polygon |
ユーザー | 0w1 |
提出日時 | 2018-10-18 23:22:04 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 2,702 ms |
コンパイル使用メモリ | 205,812 KB |
実行使用メモリ | 5,316 KB |
最終ジャッジ日時 | 2023-08-09 06:31:07 |
合計ジャッジ時間 | 4,036 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
4,932 KB |
testcase_01 | AC | 45 ms
4,752 KB |
testcase_02 | AC | 44 ms
5,212 KB |
testcase_03 | AC | 45 ms
4,740 KB |
testcase_04 | AC | 43 ms
4,800 KB |
testcase_05 | AC | 45 ms
4,808 KB |
testcase_06 | AC | 44 ms
4,892 KB |
testcase_07 | AC | 44 ms
5,316 KB |
testcase_08 | AC | 43 ms
4,932 KB |
testcase_09 | AC | 32 ms
4,808 KB |
ソースコード
#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 == -1 vector<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; }