Kattis

ne hundred years from now, in $2117$

This year there are $n$

Like today, the score of a team is a pair of integers $(a, b)$

Consider two teams $t_{1}$

You would like to follow the performance of your favorite team. Unfortunately, the organizers of GCPC do not provide a scoreboard. Instead, they send a message immediately whenever a team solves a problem.

Input

The first line of input contains two integers $n$

Then follow $m$

Output

Output $m$

Sample Input 1

3 4
2 7
3 5
1 6
1 9

Sample Output 1

题意:好多队伍比赛,按照事件发生顺序给你队伍AC题目的信息,x队AC一道题,罚时为y,每有一个队过题输出编号为1的队伍的排名
我们每当每个队A题的时候把他原来状态删除,把新状态加入到treap.由于可能有好几个队A题数罚时都一样,这样按照队伍编号升序
我们每个节点上我们设置有多个队伍就行了

  1 #include <bits/stdc++.h>
  2 #define rep(i,a,n) for (int i=a;i<=n;i++)
  3 #define per(i,a,n) for (int i=n;i>=a;i--)
  4 #define pb push_back
  5 #define mp make_pair
  6 #define all(x) (x).begin(),(x).end()
  7 #define fi first
  8 #define se second
  9 #define SZ(x) ((int)(x).size())
 10 using namespace std;
 11 typedef vector<int> vi;
 12 typedef long long ll;
 13 typedef pair<int,int> pii;
 14 const ll mod=1000000007; 
 15 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
 16 const int maxn=1e5+10;
 17 struct Node
 18 {
 19     Node *ch[2];//0 左儿子(名次靠前) 1右儿子(名次靠后)
 20     int r;//随机优先级,数值越大优先级越高
 21     int v;//值
 22     int s;//以他为根的子树上队伍数的个数
 23     int num;//当前节点上队伍数目(有队伍会题数罚时都相同)一个节点可以右多个队伍
 24     int tim;//罚时
 25     Node(int v,int tim):v(v),tim(tim){ch[0]=ch[1]=NULL;r=((rand()<<15)|rand());s=1;num=1; }
 26     inline int cmp(int x,int xtim) const {//比较函数 相等-1 名次靠前0(左子树) 名次靠后 1(右子树)
 27         if(x==v&&tim==xtim) return -1;//相等
 28         if(x==v) return xtim<tim?0:1;//题数相同罚时少的优先
 29         return x>v?0:1;
 30     }
 31     inline void maintain() {
 32         s=num;//当前节点子树个数
 33         if(ch[0]!=NULL) s+=ch[0]->s;//加上自己左子树
 34         if(ch[1]!=NULL) s+=ch[1]->s;//加上自己右子树
 35     }
 36 };
 37 void  rotate(Node* &o,int d) {//旋转
 38     Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
 39     o->maintain();
 40     k->maintain();
 41     o=k;
 42 }
 43 void insert(Node* &o,int x,int tim) {//将 过了x题罚时tim的队伍插入到treap
 44     if(o==NULL) {
 45         o=new Node(x,tim);
 46     }
 47     else {
 48         int d;
 49         if(x>o->v) {//题数多 查到左子树
 50             d=0;
 51         }
 52         else if(x==o->v) {//题数一样
 53             if(tim<o->tim) d=0;//罚时少 左子树
 54             else d=1;//罚时多 右子树
 55         }
 56         else d=1;//题数少 右子树
 57         if(x==o->v&&tim==o->tim) {//找到当前自己题数罚时都一样的节点
 58             (o->s)++;//当前节点子树的节点上的队伍数++
 59             (o->num)++;//在该节点的队伍数++
 60         }
 61         else  {
 62             insert(o->ch[d],x,tim);if(o->ch[d]->r > o->r) rotate(o,d^1);
 63         }
 64     }
 65     o->maintain();
 66 }
 67 void remove(Node* &o,int x,int tim) {
 68     int d=o->cmp(x,tim);
 69     if(d==-1) {
 70         if(o->num==1) {//如果处于当前题数罚时的队伍就一个队
 71             Node* u=o;
 72             if(o->ch[0]!=NULL&&o->ch[1]!=NULL) {
 73                 int d2=(o->ch[0]->r>o->ch[1]->r?1:0);
 74                 rotate(o,d2);
 75                 remove(o->ch[d2],x,tim);
 76             }
 77             else {
 78                 if(o->ch[0]==NULL) o=o->ch[1];
 79                 else o=o->ch[0];
 80                 delete u;
 81             }
 82         }
 83         else {//否则直接当前节点队伍数--
 84             (o->num)--;
 85         }
 86     }
 87     else {
 88         remove(o->ch[d],x,tim);
 89     }
 90     if(o!=NULL) o->maintain();
 91 }
 92 int Rank(Node* o,int x,int tim) {
 93     if(o==NULL) return 0;
 94     int s=(o->ch[0]==NULL?0:o->ch[0]->s);//s是o的左子树上队伍的个数
 95     if(o->v==x&&o->tim==tim) {//找到当前队伍状态的节点
 96         return s+1;//返回左子树队伍数+1
 97     }
 98     else if(o->v<x||(o->v==x&&o->tim>tim)) {//排名在当前节点之前,往左子树找
 99         return Rank(o->ch[0],x,tim);
100     }
101     else {//排名在当前节点之后,排名为当前节点左子树队伍数+当前节点队伍数+往右子树找
102         return Rank(o->ch[1],x,tim)+s+(o->num);
103     }
104 }
105 int nownum[maxn],nowtim[maxn];
106 int main()
107 {
108     Node *root=NULL;//初始化
109     int n,m;
110     scanf("%d%d",&n,&m);
111     int u,v;
112     rep(i,1,n) insert(root,0,0);//大家一开始都没过题
113     rep(i,1,m) {
114         scanf("%d%d",&u,&v);
115         remove(root,nownum[u],nowtim[u]);//移除当前队伍之前的状态
116         nownum[u]++;//题数加1
117         nowtim[u]+=v;//加罚时
118         insert(root,nownum[u],nowtim[u]);//插入当前状态
119         printf("%d
",Rank(root,nownum[1],nowtim[1]));//查询队伍编号为1的名次
120     }
121     return 0;
122 }
123 /**
124 3 10
125 2 1
126 2 1
127 3 1
128 1 1
129 3 5
130 3 5
131 1 1
132 1 2
133 3 1
134 
135 */