結果

問題 No.743 Segments on a Polygon
ユーザー chocoruskchocorusk
提出日時 2018-10-05 21:45:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 806 bytes
コンパイル時間 1,013 ms
コンパイル使用メモリ 84,800 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 07:51:44
合計ジャッジ時間 2,292 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
6,816 KB
testcase_01 AC 76 ms
6,820 KB
testcase_02 AC 75 ms
6,816 KB
testcase_03 AC 76 ms
6,816 KB
testcase_04 AC 75 ms
6,820 KB
testcase_05 AC 76 ms
6,816 KB
testcase_06 AC 76 ms
6,820 KB
testcase_07 AC 76 ms
6,820 KB
testcase_08 AC 75 ms
6,816 KB
testcase_09 AC 66 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int bit[200001], m;
 
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=(i&(-i));
	}
	return s;
}
 
void add(int i){
	while(i<=m){
		bit[i]+=1;
		i+=(i&(-i));
	}
}

int main()
{
	int n; cin>>n>>m;
  vector<P> v;
  for(int i=0; i<n; i++){
      int a, b; cin>>a>>b; a++; b++;
    if(a>b) swap(a, b);
    v.push_back(P(a, b));
  }
  sort(v.begin(), v.end());
  ll ans=0;
  for(int i=0; i<n; i++){
    int a=v[i].first, b=v[i].second;
    ans+=((ll)(sum(b)-sum(a)));
    add(b);
  }
  cout<<ans<<endl;
	return 0;
}
0