提出 #53851581

---

ソースコード 拡げる

// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define lll __int128
const int N = 1e6 + 5;

//树状数组 [1,n]
struct BIT {
    ll n;
    vl tree;
    void init(ll n) { //初始化
        this->n = n;
        this->tree = vl(n + 1);
    }
    ll lowbit(ll x) {
        return x & (-x);
    }
    void upd(ll x, ll d) { //单修
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }
    ll query(ll x) { //查[1,x]
        ll ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
    ll query(ll l, ll r) { //查[l,r]
        return query(r) - query(l - 1);
    }
} bt;

void solve() {
	ll n;
	cin >> n;
	vector<pll> v(n + 1);
	set<ll> s;
	for (ll i = 1; i <= n; i++) {
		cin >> v[i].fi >> v[i].se;
		s.insert(v[i].fi);
		s.insert(v[i].se);
	}
	map<ll, ll> mp;
	ll id = 1;
	for (ll x : s) {
		mp[x] = id++;
	}
	bt.init(id);
	for (ll i = 1; i <= n; i++) {
		v[i].fi = mp[v[i].fi];
		v[i].se = mp[v[i].se];
	}
	sort(v.begin() + 1, v.end());
	ll ans = 0;
	for (ll i = 1; i <= n; i++) {
		auto [l, r] = v[i];
		ans += bt.query(l, id);
		bt.upd(r, 1);
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
	solve();
	return 0;
}

提出情報

ジャッジ結果