結果
問題 | No.743 Segments on a Polygon |
ユーザー |
|
提出日時 | 2017-12-27 03:47:06 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,017 ms / 2,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 2,494 ms |
コンパイル使用メモリ | 79,264 KB |
実行使用メモリ | 71,352 KB |
最終ジャッジ日時 | 2024-11-14 07:52:44 |
合計ジャッジ時間 | 13,829 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
import java.io.File;import java.io.FileNotFoundException;import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;class Main {class BIT {int n;long[] v;public BIT(int n_) {n = n_;v = new long[n + 1];}void add(int k, int val) {while (k <= n) {v[k] += val;k += k & -k;}}long sum(int k) {long ret = 0;while (k >= 1) {ret += v[k];k -= k & -k;}return ret;}long sum(int l, int r) {return sum(r - 1) - sum(l - 1);}}void run() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int[][] a = new int[N][2];for (int i = 0; i < N; ++i) {a[i][0] = sc.nextInt();a[i][1] = sc.nextInt();if (a[i][0] > a[i][1]) {a[i][0] ^= a[i][1];a[i][1] ^= a[i][0];a[i][0] ^= a[i][1];}}Arrays.sort(a, new Comparator<int[]>() {@Overridepublic int compare(int[] arg0, int[] arg1) {return Integer.compare(arg0[0], arg1[0]);}});BIT bit = new BIT(M);long ans = 0;for (int i = 0; i < N; ++i) {ans += bit.sum(a[i][0], a[i][1]);bit.add(a[i][1], 1);}System.out.println(ans);}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}public static void main(String[] args) throws FileNotFoundException {new Main().run();}}