Log inSign up
Problems / B040

Photos that pass the contest

300 ptsCases 15Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

N photos were entered into a photo contest. The judges gave every entered photo a composition rank and a color rank. Both ranks run from 1st to Nth with one photo at each place, so no two photos share a rank. A smaller number means a better place.

The rule for sifting the photos is the following. When one other photo beats a photo in both the composition rank and the color rank, that photo is cut. Only a photo that holds its ground in at least one rank against every other photo passes.

For example, suppose the ranks of N=5 photos are the ones in the following table.

Photo12345
Composition rank54312
Color rank13524

Photo 4 is 1st in composition and 2nd in color. Photo 2 is 4th in composition and 3rd in color, so photo 4 beats it in both ranks and it is cut. Photo 3 and photo 5 are cut for the same reason, beaten by photo 4 in both ranks. Photo 1 is last in composition at 5th, but it is 1st in color, so no photo beats it in color. Photo 4 is 1st in composition, so no photo beats it in composition.

PhotoComposition rankColor rankResult
151pass
243cut
335cut
412pass
524cut

So 2 photos pass in this contest.

Walking through the photos from the best composition rank onward shows the rule. Laying the photos of the example above out by composition rank gives the following.

Composition rank12345
Photo45321
Color rank24531
Best color rank seen so far22221
Resultpasscutcutcutpass

Photo 4 has the best composition rank, so no photo can beat it in composition and it passes. Every photo after it is already beaten in composition by photo 4, so it passes only when its color rank is better than the best color rank seen so far. Photo 5, photo 3 and photo 2 fall behind the color rank of 2 and are cut, and photo 1 passes because it is 1st in color.

Given the information about several contests at once, write a program that finds how many photos pass in each contest, in order.

Input and output examples

Example 1

Input

1
5
5 1
4 3
3 5
1 2
2 4

Output

2

Example 2

Input

2
3
1 3
2 1
3 2
4
3 2
1 4
4 3
2 1

Output

2
2

Example 3

Input

1
7
1 7
4 5
5 4
7 2
2 6
3 3
6 1

Output

4

Input

  • The first line gives the number of contests T. T is a natural number less than or equal to 3.

  • The information about the T contests then follows in order. For each contest, the number of entered photos N comes on one line, and the next N lines give the composition rank and the color rank of one photo, separated by one space. N is a natural number less than or equal to 100,000.

  • The composition ranks and the color ranks each hold every natural number from 1 to N exactly once. The photos come in an order unrelated to their ranks.

Output

  • For each contest, print the number of photos that pass, one per line, in the order the contests are given.

  • Print one number per line and then a newline.

Requirements

  • Read the input from standard input and write the answer to standard output
  • A photo is cut only when it is beaten in both ranks. A photo beaten in just one rank is not cut for that reason
  • A smaller number means a better place. The photo that is 1st in composition is beaten in composition by no photo
  • Several contests are given, so take care not to carry the result of one contest over to the next
  • N goes up to 100,000, so pairing the photos up two at a time and comparing every pair does not finish in time
  • Print one number and a newline for each contest
  • Grading compares the output with the expected value down to the last character
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 15 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.

Input
Expected output
1
5
5 1
4 3
3 5
1 2
2 4
2
2
3
1 3
2 1
3 2
4
3 2
1 4
4 3
2 1
2
2
1
7
1 7
4 5
5 4
7 2
2 6
3 3
6 1
4

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 204ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal2501ms459 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.