結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-11 13:15:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 903 ms |
コンパイル使用メモリ | 88,380 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:40:21 |
合計ジャッジ時間 | 1,929 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:76:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:82:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 82 | scanf("%d%d", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 743.cc: No.743 Segments on a Polygon - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 100000;const int MAX_M = 200000;/* typedef */typedef long long ll;typedef pair<int,int> pii;template <typename T, const int MAX_N>struct BIT {int n;T bits[MAX_N + 1];BIT() {}void init(int _n) {n = _n;memset(bits, 0, sizeof(bits));}T sum(int x) {T s = 0;while (x > 0) {s += bits[x];x -= (x & -x);}return s;}void add(int x, T v) {while (x <= n) {bits[x] += v;x += (x & -x);}}};/* global variables */BIT<int,MAX_M+1> bit;pii rs[MAX_N];/* subroutines *//* main */int main() {int n, m;scanf("%d%d", &n, &m);bit.init(m + 1);for (int i = 0; i < n; i++) {int a, b;scanf("%d%d", &a, &b);if (a > b) swap(a, b);rs[i] = pii(a, b);}sort(rs, rs + n);ll sum = 0;for (int i = 0; i < n; i++) {int a = rs[i].first, b = rs[i].second;a++, b++;int d = bit.sum(b) - bit.sum(a);sum += d;//for (int i = 1; i <= m; i++) printf("%d ", bit.sum(i));//printf("%d-%d: d=%d\n", a, b, d);bit.add(b, 1);}printf("%lld\n", sum);return 0;}