## 10587 - Mayor's posters

Moderator: Board moderators

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

### 10587 - Mayor's posters

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Sort the intervals by x, then y, and scan.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
Larry wrote: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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Larry wrote:Sort the intervals by x, then y, and scan.
Could you give more detail description?
Thx

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
Larry wrote: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
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
Tomson wrote:
Larry wrote: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
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
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
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm

### 10587

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
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### Re: [10587]

miko'mized wrote: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

2

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### Re: [10587]

miko'mized wrote: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

2

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Obviously, this input/output pair is wrong........
It confuses me for few days until I read the problem for many many times and make sure I understand the problem correctly........
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
.. wrote:Obviously, this input/output pair is wrong........
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

2

Sorry again.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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