Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using std::vector;
- using std::cin;
- using std::cout;
- using std::pair;
- struct Node{
- long long cnt = 0;
- int tl;
- int tr;
- int left = -1;
- int right = -1;
- Node(int l, int r) {
- tl = l;
- tr = r;
- }
- };
- class DynTree {
- private:
- vector<Node> T;
- public:
- DynTree() {
- T.push_back(Node(0, INT_MAX));
- }
- void Update(int v, int pos, int delta);
- long long Get(int v, int pos) const;
- };
- void DynTree::Update(int v, int pos, int delta) {
- T[v].cnt += delta;
- if (T[v].tl == T[v].tr) {
- return;
- }
- const int tm = (T[v].tl + T[v].tr) >> 1;
- if (T[v].left == -1 && pos <= tm) {
- T.push_back(Node(T[v].tl, tm));
- T[v].left = T.size() - 1;
- }
- if (pos <= tm) {
- Update(T[v].left, pos, delta);
- }
- if (T[v].right == -1 && pos > tm) {
- T.push_back(Node(tm + 1, T[v].tr));
- T[v].right = T.size() - 1;
- }
- if (pos > tm) {
- Update(T[v].right, pos, delta);
- }
- }
- long long DynTree::Get(int v, int pos) const {
- if (pos == T[v].tl) {
- return T[v].cnt;
- }
- const int tm = (T[v].tl + T[v].tr) >> 1;
- long long ans = 0;
- if (pos <= tm) {
- if (T[v].left != -1) {
- ans += Get(T[v].left, pos);
- }
- if (T[v].right != -1) {
- ans += Get(T[v].right, tm + 1);
- }
- }
- else{
- if (T[v].right != -1) {
- ans += Get(T[v].right, pos);
- }
- }
- return ans;
- }
- bool cmp(std::pair<int, int> p1, std::pair<int, int> p2){
- if ((p1.first < p2.first) || (p1.first == p2.first && p1.second > p2.second)) {
- return true;
- }
- return false;
- }
- int main(){
- std::ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin >> n;
- vector<pair<int, int>> segments(n);
- int left, right;
- for (int i = 0; i < n; ++i) {
- std::cin >> left >> right;
- segments[i] = {left, right};
- }
- sort(segments.begin(), segments.end(), cmp);
- DynTree tree;
- long long ans = 0;
- int cnt = 0;
- int pleft = segments[0].first, pright = segments[0].second;
- for (int i = 0; i < segments.size(); ++i) {
- if (segments[i].first == pleft && segments[i].second == pright) {
- ++cnt;
- }
- else {
- tree.Update(0, pright, cnt);
- cnt = 1;
- pleft = segments[i].first;
- pright = segments[i].second;
- }
- ans += tree.Get(0, segments[i].second);
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement