10587 - Mayor's posters

[Tomson]

How to solve it ? I always got TLE.
Could anybody give me some hints?
Thanks very much!

[Larry]

Sort the intervals by x, then y, and scan.

[rotoZOOM]

Sort the intervals by x, then y, and scan.

What y ?
Sort just by X. ))
Do not forget that left X and right X of poster is not the same things ))

[Larry]

Heh, you probably don't need a y, but I made it simpler by putting a y for the positiion of the posters, made it easier.

[windows2k]

Sort the intervals by x, then y, and scan.

I don't know your meaning.
Could you give more detail description?
Thx

[Larry]

There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..

[Tomson]

There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..

Oh, I still cannot understand your meaning.
Could you give me some more explanation?
Thanks,!!!

[rotoZOOM]

There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..

Oh, I still cannot understand your meaning.
Could you give me some more explanation?
Thanks,!!!

I'll try to explain.
All posters have two X-coordinates (left and right)
We sort all X-coordinates and remember which posters it relate to, and what bound it is (left or right).
Then we go through all sorted X from left to right and if current coordinate is left boundary we add in stack number of poster (then number more then poster higher over other posters, Do you understand what I mean ?).
If current coordinate is right boundary we remove from stack number of poster related to this coordinate. Then If current X coordinate does not coincide with previous one we remember number of poster which number is highest in stack.
I hope you understand my explanation.
Sorry for my english.

[Tomson]

Thank you very much! I almost understand your meaning.
And finally, I solved it using a heap, it seems that 's faster than a array. my program solved it during 00.5 s.

Thank you anyway!

[miko'mized]

I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?

[rotoZOOM]

I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?

Try this one:
1
3
1 4
5 10
3 7

Right answer is:
2

[rotoZOOM]

I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?

Try this one:
1
3
1 4
5 10
3 7

Right answer is:
2

[..]

Obviously, this input/output pair is wrong........
Please delete/correct it
It confuses me for few days until I read the problem for many many times and make sure I understand the problem correctly........

[rotoZOOM]

Obviously, this input/output pair is wrong........
Please delete/correct it
It confuses me for few days until I read the problem for many many times and make sure I understand the problem correctly........

Yeah, I'm sorry.
My bug.
Correct input is:
1
3
3 7
1 4
5 10

Right answer is:
2

Sorry again.

[Emilio]

Hi there fellow sufferers!

This problem seem me easy, but I'm getting WA and can't encounter any case where my code fails.
Could anyone take a look to my code or give me some good test cases where my code fails?

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;
}

P.S. Sorry for posting code