当前位置：首页 > news >正文

打卡信奥刷题（3078）用C++实现信奥题 P7033 [NWRRC 2016] CodeCoder vs TopForces

news 2026/7/26 17:00:23

P7033 [NWRRC 2016] CodeCoder vs TopForces

题目描述

在 Byteland，竞赛编程非常流行。事实上，每位 Byteland 的公民都在两个编程网站——CodeCoder 和 TopForces 上注册。每个网站都有自己专有的评分系统。每位公民在每个网站上都有一个唯一的整数评分，代表他们的技能。评分越高，技能越好。

Byteland 的人天生乐观。公民 A 认为，如果存在一个 Byteland 公民的序列A=P0,P1,...,Pk=BA = P_{0}, P_{1},...,P_{k} = BA=P0,P1,...,Pk=B，对于某个k≥1k \ge 1k≥1，使得对于每个i(0≤i<k)i (0 \le i < k)i(0≤i<k)，PiP_{i}Pi在一个或两个网站上的评分都高于Pi+1P_{i+1}Pi+1，那么他就有机会在编程比赛中击败公民 B。

每位 Byteland 公民都想知道他们在编程比赛中可能击败多少其他公民。

输入格式

输入的第一行包含一个整数nnn——公民的数量(1≤n≤100000)(1 \le n \le 100 000)(1≤n≤100000)。接下来的nnn行包含关于评分的信息。第iii行包含两个整数CCiCC_{i}CCi和TFiTF_{i}TFi——第iii位公民在 CodeCoder 和 TopForces 上的评分(1≤CCi,TFi≤106)(1 \le CC_{i}, TF_{i} \le 10^{6})(1≤CCi,TFi≤106)。每个网站上的所有评分都是不同的。

输出格式

对于每位公民iii，输出一个整数bib_{i}bi——他们在编程比赛中可能击败的其他公民数量。每个bib_{i}bi应该单独一行输出，顺序与输入中给出的公民顺序相同。

输入输出样例 #1

输入 #1

4 2 3 3 2 1 1 4 5

输出 #1

2 2 0 3

说明/提示

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>usingnamespacestd;structnode{inted[5],id,T,C;}di[114514];boolcmp(node i,node j){returni.C<j.C;}boolpmc(node i,node j){returni.T<j.T;}intans[114514],n,t[114514],su;//ed[] 和 id 存原编号，t[i] 存 i 现编号boolused[114514];voiddfs(intpos){su++;used[pos]=true;for(inti=1;i<=di[pos].ed[0];i++){intnxt=t[di[pos].ed[i]];if(!used[nxt])dfs(nxt);}}intmain(){cin>>n;for(inti=1;i<=n;i++){di[i].id=i;cin>>di[i].C>>di[i].T;}sort(di+1,di+n+1,cmp);for(inti=2;i<=n;i++){di[i].ed[++di[i].ed[0]]=di[i-1].id;}sort(di+1,di+n+1,pmc);for(inti=1;i<=n;i++){t[di[i].id]=i;if(i==1)continue;di[i].ed[++di[i].ed[0]]=di[i-1].id;}for(inti=1;i<=n;i++){if(!used[i])dfs(i);ans[di[i].id]=su-1;//把自己也算进去了，所以要减一}for(inti=1;i<=n;i++)cout<<ans[i]<<endl;}