結果

問題 No.743 Segments on a Polygon
コンテスト
ユーザー 王源成
提出日時 2025-12-21 20:47:15
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,040 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,802 ms
コンパイル使用メモリ 198,948 KB
実行使用メモリ 9,036 KB
最終ジャッジ日時 2025-12-21 20:47:20
合計ジャッジ時間 3,800 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,a[N],b[N],id[N]; 
bool cmp(int x,int y){
    return a[x]<a[y];
}
int c[N];
inline int l(int x){
    return x&(-x);  
}
inline void add(int x){
    while(x<=m){
        c[x]++;
        x+=l(x);
    }
    return;
}
inline int ask(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=l(x);
    }
    return res;
}
signed main(){
    //freopen("intersection.in","r",stdin);
    //freopen("intersection.out","w",stdout);
    cin>>n>>m;
    int ans=n*(n-1)/2;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;++x;++y;
        if(x>y) swap(x,y);
        a[i]=x;b[i]=y;
        id[i]=i;
    }
    sort(id+1,id+1+n,cmp);
    for(int o=1;o<=n;o++){
        int i=id[o];
        ans-=(o-1-ask(b[i]));
        add(b[i]);
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);b[0]=-1;
     
    int l=1,r=0;
    while(l<=n){
        while(r<=n&&b[r]<a[l]) r++;
        r--;
        ans-=r; 
        l++;
    } 
    cout<<ans<<'\n';
    return 0;
}
0