結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2020-06-11 01:58:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 1,740 bytes |
コンパイル時間 | 1,677 ms |
コンパイル使用メモリ | 166,636 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 22:45:51 |
合計ジャッジ時間 | 2,930 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.11 01:58:36**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template < typename T >struct BinaryIndexedTree {std::vector< T > data;BinaryIndexedTree(int sz) {data.assign(++sz, 0);}inline T sum(int k) {T ret = 0;for (++k; k > 0; k -= k & -k) ret += data[k];return (ret);}inline T sum(int left, int right) {return sum(right) - sum(left - 1);}inline void add(int k, T x) {for (++k; k < data.size(); k += k & -k) data[k] += x;}int get(ll k) {++k;int res = 0;int N = 1;while (N < (int)data.size()) N *= 2;for (int i = N / 2; i > 0; i /= 2) {if (res + i < (int)data.size() && data[res + i] < k) {k = k - data[res + i];res = res + i;}}return res + 1;}void print() {std::cout << "[ ";for (int i = 0; i < data.size() - 1; i++) {std::cout << sum(i, i);if (i < data.size() - 2) cout << ", ";}std::cout << " ]" << endl;}};int main() {int n, m;cin >> n >> m;BinaryIndexedTree< int > bit(m);ll ans = 0;vector< pair< int, int > > p(n);for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;if (a > b) swap(a, b);p[i].first = a;p[i].second = b;}sort(p.begin(), p.end());for (int i = 0; i < n; i++) {ans += bit.sum(p[i].first, p[i].second);bit.add(p[i].second, 1);}cout << ans << endl;return 0;}