Nordic Collegiate Programming Contest NCPC 2017-Problem G Galactic Collegiate Programming Contest

时间：2024-06-14 15:35:56

题目大意：有n( n<1e5 )只队伍参加程序竞赛，然后给m个信息，每个信息告诉你第p

个队伍过了一题，并且告诉你罚时是多少，让你输入每个信息之后，第一个队伍的

排名。

思路：一眼看过去就像数据结构题，我们可以用足够大的数表示过了一题然后减去罚时，

这样就可以用一个数值来确定排名，然后我们用将所有出现过的分数抽离出来，排序去重

用这些数离散化用树状数组维护各个分数队伍数的前缀和，这样就能快速计算排名。

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const double g=10.0,eps=1e-;

 const int N=+,maxn=,inf=0x3f3f3f3f;

 int te[N],pe[N],cnt;

 ll pen[N],has[N];

 ll sum[N];

 void update(int i,ll v)

 {

     while(i<cnt)

     {

         printf("%d %d**\n",i,cnt);

         sum[i]+=v;

         i+=i&(-i);

     }

 }

 ll query(int i)

 {

     ll ans=;

     while(i>)

     {

         ans+=sum[i];

         i-=i&(-i);

     }

     return ans;

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     cnt=;

     has[cnt++]=;

     for(int i=;i<m;i++)

     {

         scanf("%d%d",&te[i],&pe[i]);

         pen[te[i]]+=1e10-pe[i];

         has[cnt++]=pen[te[i]];

     }

     sort(has+,has+cnt);

     cnt=unique(has+,has+cnt)-has;

     memset(pen,,sizeof pen);

     update(,n);

     for(int i=;i<m;i++)

     {

         int p=lower_bound(has+,has+cnt,pen[te[i]])-has;

         update(p,-);

         pen[te[i]]+=1e10-pe[i];

         p=lower_bound(has+,has+cnt,pen[te[i]])-has;

         update(p,);

         p=lower_bound(has+,has+cnt,pen[])-has;

         int res=query(cnt-)-query(p);

         printf("%d\n",res+);

     }

     return ;

 }

 /********************

 ********************/

相关文章