BUPT校内训练 Codeforces Gym 101572 G Galactic Collegiate Programming Contest 离散化+树状数组计数

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

一场ICPC赛制比赛,有n支队伍和m次正确提交

每次正确提交包含a,b两个参数,a表示队伍编号,b表示此题的罚时。

要求对于每次事件,输出1号队伍的排名(并列的算同样的排名)

具体排名方法为:通过题目数多的队伍排名靠前,通过题目数相同的队伍总罚时低的靠前。

题解&分析

如果暴力做的话,每一修改O(1),排序查询O(nlogn),总复杂度O(mnlogn),这对于10^6的数据是不现实的。

我们要求做到O(nlogn),也就是说不能有每修改一次就排序的操作。

我们可以注意到,每一次事件发生后,只会有一个队伍的成绩发生变化,其余的成绩是不动的。

所以我们可以读入所有数据,然后计算每一次事件发生后出现的成绩二元组(通过题目数,总罚时)。这样我们可以预处理出所有可能的成绩。

之后对所有成绩排序并离散化标号,保证成绩高的离散化后标号较小。

之后我们从头开始模拟每一次事件发生。

对于每一次事件,某一个队伍成绩发生变化,从(a,b)变为(a+1,b+t),而这两个二元组都有与之对应的离散化标号。

于是我们可以考虑使用树状数组(或者线段树,不过树状数组的常数较小)对于当前所有队伍的成绩二元组进行统计。

对每一次事件,(a,b)对应的标号位置数目-1,(a+1,b+t)对应的标号位置数目+1,表示某只对于的成绩发生变化,从(a,b)变为(a+1,b+t)

每次修改完以后查询当前1号队伍的成绩二元组(nowpass,nowtime)所对应的标号之前的一共有多少支队伍,假设为k,则k+1即为当前1号队伍的排名。

 代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<1) + (num<<3) + c - '0';
    return (flag ? -1 : 1) * num;
}
typedef pair<int,int> P;
const int maxn = 1e5+5;
map<P,int>mp;
int c[maxn<<1];
int lowbit(int x){
    return (x & -x);
}
void update(int now,int k){
    for(int i = now;i < maxn;i += lowbit(i)){
        c[i] += k;
    }
    return;
}
int query(int now){
    int ret = 0;
    if(now == 0)return 0;
    while(now > 0){
        ret += c[now];
        now -= lowbit(now);
    }
    return ret;
}
P nowscore;
int cnt = 0;
int a[maxn],b[maxn];
P p[maxn];
int n,k;
int u[maxn],s[maxn];
int num = 0;
bool cmp(P x,P y){
    return (x.first > y.first || (x.first == y.first && x.second < y.second));
}
int main(){
    n = get_num();
    k = get_num();
    nowscore = make_pair(0,0);
    p[0] = nowscore;
    for(int i = 1;i <= k;++i){
        u[i] = get_num();
        s[i] = get_num();
        a[u[i]]++;
        b[u[i]] += s[i];
        p[++cnt] = make_pair(a[u[i]],b[u[i]]);
    }
    sort(p,p+cnt+1,cmp);
    num = 1;
    mp[p[0]] = num;
    for(int i = 1;i <= cnt;++i){
        if(p[i] != p[i-1]){
            num++;
            mp[p[i]] = num;
        }
    }
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    update(mp[nowscore],n);
    for(int i = 1;i <= k;++i){
        P x = make_pair(a[u[i]],b[u[i]]);
        update(mp[x],-1);
        a[u[i]]++;
        b[u[i]] += s[i];
        x.first++;
        x.second += s[i];
        update(mp[x],1);
        if(u[i] == 1){
            nowscore.first++;
            nowscore.second += s[i];
        }
        int pos = mp[nowscore];
        int y = query(pos-1);
        printf("%d\n",y+1);
    }
    return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00