結果

問題 No.743 Segments on a Polygon
ユーザー rpy3cpp
提出日時 2019-05-15 00:31:53
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 28 ms
コード長 948 Byte
コンパイル時間 1,284 ms
使用メモリ 4,368 KB
最終ジャッジ日時 2020-01-23 20:57:53

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 28 ms
4,328 KB
2.txt AC 28 ms
4,312 KB
3.txt AC 24 ms
4,352 KB
4.txt AC 28 ms
4,264 KB
5.txt AC 28 ms
4,368 KB
6.txt AC 28 ms
4,276 KB
7.txt AC 28 ms
4,352 KB
8.txt AC 28 ms
4,328 KB
9.txt AC 28 ms
4,304 KB
challenge_01.txt AC 24 ms
4,276 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

struct BIT{
    vector<int> bit;
    BIT(int n) : bit(n, 0){}
    int range_sum(int i, int j) {return sum(j) - sum(i - 1);}
    // return sum of v[i] to v[j] including both ends.
    int sum(int j){
        int s = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) s += bit[j];
        return s;
    }
    void add(int k, int a) {for (; k < bit.size(); k |= k + 1) bit[k] += a;}
};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> Es(M, -1);
    for (int i = 0; i < N; ++i){
        int a, b;
        cin >> a >> b;
        if (a > b){
            Es[b] = a;
        }else{
            Es[a] = b;
        }
    }
    BIT bit(M);
    long long cnt = 0;
    for (int a = 0; a < M; ++a){
        if (Es[a] == -1) continue;
        cnt += 1LL * bit.range_sum(a, Es[a]);
        bit.add(Es[a], 1);
    }
    cout << cnt << endl;
    return 0;
}
0