結果
問題 | No.743 Segments on a Polygon |
ユーザー |
![]() |
提出日時 | 2018-10-06 07:37:49 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,531 bytes |
コンパイル時間 | 1,832 ms |
コンパイル使用メモリ | 166,268 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 08:05:09 |
合計ジャッジ時間 | 3,083 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;#define fi first#define se second#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)#define rep(i,n) repl(i,0,n)#define all(x) (x).begin(),(x).end()#define dbg(x) cout<<#x"="<<x<<endl#define mmax(x,y) (x>y?x:y)#define mmin(x,y) (x<y?x:y)#define maxch(x,y) x=mmax(x,y)#define minch(x,y) x=mmin(x,y)#define uni(x) x.erase(unique(all(x)),x.end())#define exist(x,y) (find(all(x),y)!=x.end())#define bcnt __builtin_popcountll#define INF 1e16#define mod 1000000007struct BIT{int n;vector<ll> bit;BIT(int size):n(size),bit(size+1,0){}ll sum(int i){ll s=0;while(i>0){s+=bit[i];i-=i&-i;}return s;}void add(int i,ll v){if(i==0)return ;while(i<=n){bit[i]+=v;i+=i&-i;}}ll lower_bound(ll w){if(w<=0)return 0;ll x=0,r=1;while(r<n)r<<=1;for(ll k=r;k>0;k>>=1){if(x+k<=n&&bit[x+k]<w){w-=bit[x+k];x+=k;}}return x+1;}};int N,M;int A[100010],B[100010];vector<int> idx;int main(){cin>>M>>N;rep(i,M){cin>>A[i]>>B[i];if(A[i]>B[i])swap(A[i],B[i]);idx.push_back(i);}sort(all(idx),[=](const int& a,const int& b){ return B[a] < B[b]; });ll res=0;BIT bit(N);rep(i,M){ll l=A[idx[i]]; ll r=B[idx[i]];res+=bit.sum(r+1)-bit.sum(l);bit.add(l+1,-1); bit.add(r+1,+1);}cout<<res<<endl;return 0;}