結果

問題 No.743 Segments on a Polygon
ユーザー rpy3cpp
提出日時 2019-05-15 00:31:53
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 30 ms
コード長 948 Byte
コンパイル時間 1,263 ms
使用メモリ 2,884 KB
最終ジャッジ日時 2019-09-19 21:44:22

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 28 ms
2,884 KB
2.txt AC 28 ms
2,880 KB
3.txt AC 29 ms
2,880 KB
4.txt AC 28 ms
2,884 KB
5.txt AC 28 ms
2,884 KB
6.txt AC 29 ms
2,884 KB
7.txt AC 29 ms
2,884 KB
8.txt AC 30 ms
2,880 KB
9.txt AC 29 ms
2,880 KB
challenge_01.txt AC 24 ms
2,884 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