結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-05 21:45:58 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#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;}