Line Intersections

input/code.cpp: In function 'void Test()':
input/code.cpp:146:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     freopen("temp\\in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int N = 100005, M = 1e6+1;

/*----------------------------------------------------------------------------*/
template<typename Value, typename Tag>
struct Node
{
    int id, l, r;
    Value val;
    Tag tag;

    inline int length()const
    {
        return r-l+1;
    }
    inline bool disjoint(const int& l_bor, const int& r_bor)const
    {
        return l_bor>r || r_bor<l;
    }// (l, r<l_bor)/(r_bor>l, r)
    inline bool subset(const int& l_bor, const int& r_bor)const
    {
        return l_bor<=l && r_bor>=r;
    }// [l_bor, l, r, r_bor]
};

template<typename Value, typename Tag>
class SegmentTree
{
  public:
    typedef Value (*FucMer)(Value, Value);
    typedef void (*FucCov)(Node<Value, Tag>*, Tag);
    SegmentTree(const FucMer f1, const FucCov f2, Value val, Tag tag)
        : Merge(f1), Cover(f2), val_zero_(val), tag_zero_(tag) {}
    void Init(const int& size, const vector<Value>& v)
    {
        l_range_=1, r_range_=size;
        nodes_.resize(size<<2);
        Build(1, l_range_, r_range_, v);
    }

    inline Node<Value, Tag>* identify(const int& p)
    {
        return &nodes_[p];
    }
    inline Node<Value, Tag>* l_child(const Node<Value, Tag>* p)
    {
        return &nodes_[p->id<<1];
    }// 2*id for the left child
    inline Node<Value, Tag>* r_child(const Node<Value, Tag>* p)
    {
        return &nodes_[p->id<<1|1];
    }// 2*id+1 for the right child

    void Modify(const int& pos, const Tag& tag)
    {
        Modify(identify(1), pos, pos, tag);
    }// point change
    void Modify(const int& l_bor, const int& r_bor, const Tag& tag)
    {
        Modify(identify(1), l_bor, r_bor, tag);
    }// section change
    Value Query(const int& pos)
    {
        return Query(identify(1), pos, pos);
    }// point query
    Value Query(const int& l_bor, const int& r_bor)
    {
        return Query(identify(1), l_bor, r_bor);
    }// section query

  private:
    const FucMer Merge;
    const FucCov Cover;
    const Value val_zero_;
    const Tag tag_zero_;
    int l_range_, r_range_;
    vector<Node<Value, Tag>> nodes_;

    inline void PushUp(Node<Value, Tag>* p)
    {
        p->val=Merge(l_child(p)->val, r_child(p)->val);
    }
    inline void PushDown(Node<Value, Tag>* p)
    {
        Cover(l_child(p), p->tag);
        Cover(r_child(p), p->tag);
        p->tag=tag_zero_;
    }

    void Build(int cur, int l_cur, int r_cur, const vector<Value>& v)
    {
        Node<Value, Tag> *p=identify(cur);
        p->id=cur, p->l=l_cur, p->r=r_cur;
        p->tag=tag_zero_;
        if(l_cur>r_cur) return;
        if(l_cur==r_cur) { p->val=v[l_cur]; return; }
        int mid=(l_cur+r_cur)>>1;
        Build(cur<<1, l_cur, mid, v);
        Build(cur<<1|1, mid+1, r_cur, v);
        PushUp(p);
    }

    void Modify(Node<Value, Tag> *p, const int& l_bor, const int& r_bor,
                const Tag& tag)
    {
        if(p->disjoint(l_bor, r_bor)) return;
        if(p->subset(l_bor, r_bor)) { Cover(p, tag); return; }
        if(p->tag!=tag_zero_) PushDown(p);
        Modify(l_child(p), l_bor, r_bor, tag);
        Modify(r_child(p), l_bor, r_bor, tag);
        PushUp(p);
    }

    Value Query(Node<Value, Tag>* p, const int& l_bor, const int& r_bor)
    {
        if(p->disjoint(l_bor, r_bor)) return val_zero_;
        if(p->subset(l_bor, r_bor))   return p->val;
        if(p->tag!=tag_zero_) PushDown(p);
        return Merge(Query(l_child(p), l_bor, r_bor), 
                     Query(r_child(p), l_bor, r_bor));
    } 
};
/*----------------------------------------------------------------------------*/

auto h1=[](int a, int b) -> int { return a + b; };
auto h2=[](Node<int, int>* p, int x) { p->val += x*p->length(), p->tag += x; };
SegmentTree<int, int> h_sum(h1, h2, 0, 0);

typedef pair<pair<int, int>, int> P;
vector<P> vertical, horizon;

bool CompareLast(const P& a, const P& b) {
    return a.second < b.second;
}
struct CompareMiddle {
    bool operator()(const P& a, const P& b) const {
        return a.first.second > b.first.second; 
    }
};

void Test()
{
    freopen("temp\\in.txt", "r", stdin);
}
int main()
{
    // Test();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int a1, b1, a2, b2;
        cin >> a1 >> b1 >> a2 >> b2;
        a1 += M, a2 += M, b1 += M, b2 += M;
        if(a1 == a2) {
            if(b1 > b2) swap(b1, b2);
            vertical.push_back(make_pair(make_pair(b1, b2), a1));
        } else {
            if(a1 > a2) swap(a1, a2);
            horizon.push_back(make_pair(make_pair(a1, a2), b1));
        }
    }
    vector<int> zeros(2*M, 0);
    h_sum.Init(2*M, zeros);

    sort(vertical.begin(), vertical.end(), CompareLast);
    sort(horizon.begin(), horizon.end());

// for(auto p: vertical)
//     cout << p.first.first << p.first.second << p.second << endl;
// for(auto p: horizon)
//     cout << p.first.first << p.first.second << p.second << endl;

    priority_queue<P, vector<P>, CompareMiddle> list;
    auto it = horizon.begin();
    P now_p, now_q;
    int now = -1e7, sum = 0;
    pair<int, int> temp;
    for(auto p : vertical)
    {
        temp = p.first;
        now = p.second;
        // Delete old ones
        while(!list.empty() && list.top().first.second <= now)
        {
            now_p = list.top(); list.pop();
            h_sum.Modify(now_p.second, -1);
        }
        // Enter new ones
        while(it != horizon.end())
        {
            now_q = *it;
            if(now_q.first.first > now) break;
            h_sum.Modify(now_q.second, 1);
            list.push(now_q);
            it++;
        }
        sum += h_sum.Query(temp.first, temp.second);
    }
    cout << sum;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER