OJ Board

Code: Select all

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>
#include <cassert>
#include <list>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;

struct lrn {int lr,n;};
struct comp_lrn
{
    bool operator () (lrn a, lrn b) const
    {
        return a.lr<b.lr;
    }
};
set<lrn,comp_lrn> wall;
set<int> difs;

int main ()
{
    set<lrn,comp_lrn>::iterator it, itend;
    set<int>::iterator itd;
    lrn g;
    int casos, N, l, r, i;
    
    cin >> casos;
    while (casos--)
    {
        cin >> N;
        wall.clear();
        for (i=0; i<N; i++)
        {
            cin >> l >> r;
            
            /* I hide the limits of other possible coincident posters */
            g.lr=l, wall.erase(g);
            g.lr=r, wall.erase(g);
            /* I insert this new poster */
            g.lr=l, g.n=i, wall.insert(g);
            g.lr=r, g.n=i, wall.insert(g);
            /* If l==r all the possible limits poster that must be deleted was already deleted */
            if (l==r) continue;
            /* I find the limits of the new poster in the data structure */
            g.lr=l, it=wall.find(g);
            g.lr=r, itend=wall.find(g);
            difs.clear();
            for (++it; it!=itend; ++it)
            {
                /* I store the limits of some posters hidden by the new poster */
                difs.insert((*it).lr);
            }
            /* I erase all the poster limits hidden by the new poster */
            for (itd=difs.begin(); itd!=difs.end(); ++itd)
            {
                g.lr=*itd;
                wall.erase(g);
            }
        }
        /* Finally, I make a set of all the different posters */
        difs.clear();
        for (it=wall.begin(); it!=wall.end(); ++it) difs.insert((*it).n);
        cout << difs.size() << "\n";
    }
    return 0;
}