結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-10 16:46:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 1,761 ms |
コンパイル使用メモリ | 167,908 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:40:14 |
合計ジャッジ時間 | 3,439 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = int64_t;using vi = vector<i64>;using vvi = vector<vi>;using ii = pair<int, int>;class BIT {int n;vi data;i64 sum(int i) {i64 s = 0;while (i > 0) {s += data[i];i -= i & -i;}return s;}public:BIT(int n) : n(n) {data = vi(n + 1);}void add(int i, i64 x) {i++;while (i <= n) {data[i] += x;i += i & -i;}}// [l, r)i64 sum(int l, int r) {return sum(r) - sum(l);}};int main() {int n, m;cin >> n >> m;vector<ii> vs;for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;vs.push_back(ii(min(a, b), max(a, b)));}sort(vs.begin(), vs.end());BIT bit(m);i64 cnt = 0;for (ii& p: vs) {cnt += bit.sum(p.first, p.second);bit.add(p.second, 1);}cout << cnt << endl;}