#PQJ1548x13399. QOJ 1548_13399

    ID: 2645 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训线段树

QOJ 1548_13399

Croatian Open Competition in Informatics Task Tenis Round 1, October 17th 2020 1 second / 512 MiB / 110 points Task Tenis Mirko is a big fan of tennis. Soon an important tournament with n players will take place. Mirko has spent years researching tennis players and has collected various statistics about the competitors. He has ranked their ability on three different courts: grass, clay and hard. More precisely, for each court he has determined the order (rank list) of the players, with the first player being the strongest, and the last being the weakest. On this tournament, every player will play against every other player exactly once, so there will be n(n−1) 2 matches in total. A tennis match cannot end in a draw, and the player who is stronger on the court the match is played on will win. The organisers know that, so they have decided that each match should be played on the court for which the winner will be the strongest, i.e. have the best position in the corresponding rank list. If some courts are equal in that sense (the position of the winner of the match between players A and B would be the same, e.g. player A would win on court 1, and player B on court 2, and they are both ranked third on the corresponding court rank lists), they will choose the court for which the loser would have the best position. If the courts are still equal, the one with the smallest index is chosen. Determine the outcome of this tournament: the number of matches played on each court and the number of wins for each player. Input The first line contains an integer n, the number of players. The players are labeled with integers from 1 to n. The i-th of the following three lines contains a permutation of integers from 1 to n, the rank list of the players for the i-th surface, starting with the strongest player. Output In the first line, print the number of matches played on the first, second and third surface. In the second line, print the number of matches won by each player from 1 to n. Scoring Subtask Points Constraints 1 35 1 ≤n ≤300 2 15 1 ≤n ≤3000 3 60 1 ≤n ≤100 000 If your solution prints at least one of the lines correctly on each test case of a subtask, but it doesn’t print both lines correctly on at least one test case, you will get half of the points for that subtask. 9 of 10 Croatian Open Competition in Informatics Task Tenis Round 1, October 17th 2020 1 second / 512 MiB / 110 points Examples input input 3 4 3 2 1 4 3 2 1 1 3 2 3 1 2 4 3 2 1 1 2 3 4 output output 1 2 0 3 2 1 2 0 1 1 0 2 3 Clarification of the first example: The match between players 1 and 2 is played on court 2, because the winner (player 1) has the best (first) position. For the match between playes 1 and 3, the winner has the same position on all three courts, but the loser has a better position on court 2. For the match between players 2 and 3, court 1 and 3 are equal, so the one with the smaller index is chosen (court 1). 10 of 10