Submission #20580

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct AVL{
struct node{
int key;
int size,height;
node *child[2];
node (const int &key):key(key),size(1),height(1){
child[0]=child[1]=0;
}
} *root;
typedef node *pointer;
AVL(){root=NULL;}
pointer find(int key){
return find(root,key);
}
node *find(node *t,const int key){
if(t==NULL) return NULL;
if(key==(t->key)) return t;
else if(key<(t->key)) return find(t->child[0],key);
else return find(t->child[1],key);
}
void insert(const int key){
root=insert(root,new node(key));
}
node *insert(node *t,node *x){
if(t==NULL) return x;
if((x->key)<=(t->key)) t->child[0]=insert(t->child[0],x);
else t->child[1]=insert(t->child[1],x);
t->size+=1;
return balance(t);
}
void erase(const int key){
int t=key;
if(find(t)==NULL) return;
root=erase(root,key);
}
node *erase(node *t,const int x){
if(t==NULL) return NULL;
if(x==(t->key)){
return move_down(t->child[0],t->child[1]);
}else{
if(x<(t->key)) t->child[0]=erase(t->child[0],x);
else t->child[1]=erase(t->child[1],x);
t->size-=1;
return balance(t);
}
}
node *move_down(node *t,node *rhs){
if(t==NULL) return rhs;
t->child[1]=move_down(t->child[1],rhs);
return balance(t);
}
int sz(node *t){
if(t!=NULL) return t->size;
return 0;
}
int ht(node *t){
if(t!=NULL) return t->height;
return 0;
}
node *rotate(node *t,int l,int r){
node *s=t->child[r];
t->child[r]=s->child[l];
s->child[l]=balance(t);
if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;
if(s!=NULL) s->size=sz(s->child[0])+sz(s->child[1])+1;
return balance(s);
}
node *balance(node *t){
for(int i=0;i<2;i++){
if(ht(t->child[!i])-ht(t->child[i])<-1){
if(ht(t->child[i]->child[!i])-ht(t->child[i]->child[i])>0)
t->child[i]=rotate(t->child[i],i,!i);
return rotate(t,!i,i);
}
}
if(t!=NULL) t->height=max(ht(t->child[0]),ht(t->child[1]))+1;
if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;
return t;
}
pointer rank(int k){
return rank(root,k);
}
pointer rank(node *t,int k){
if(t==NULL) return NULL;
int m=sz(t->child[0]);
if(k<m) return rank(t->child[0],k);
if(k==m) return t;
if(k>m) return rank(t->child[1],k-m-1);
}
int index(int key){
if(find(key)==NULL) return -1;
return index(root,key);
}
int index(node *t,int key){
if(key==(t->key)) return sz(t->child[0]);
if(key<(t->key)) return index(t->child[0],key);
else return sz(t)-sz(t->child[1])+index(t->child[1],key);
}
};
#define MAX 114514
int x[MAX];
signed main(){
int n,q;
cin>>n>>q;
AVL avl;
set<int> s;
avl.insert(0);
s.insert(0);
map<int,int> m,l;
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==1){
int a,b;
cin>>a>>b;
l[a]++;
a=a*MAX+l[a];
if(m.count(b)&&a<=m[b]) continue;
if(m.count(b)){
avl.erase(m[b]);
s.erase(m[b]);
}
m[b]=a;
avl.insert(m[b]);
s.insert(m[b]);
}
if(t==2){
int c;
cin>>c;
//cout<<"s:";for(int j:s) cout<<" "<<j;cout<<endl;
int k=*--s.lower_bound(c*MAX);
cout<<(s.size()-1)-avl.index(k)<<endl;
}
}
return 0;
}

ステータス

項目 データ
問題 0757 - ghoststudents
ユーザー名 beet1333
投稿日時 2017-07-04 23:40:26
言語 C++17
状態 Accepted
得点 10
ソースコード長 3471 Byte
最大実行時間 414 ms
最大メモリ使用量 9992 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_01.in AC 25 ms 480 KB
1
01_small_01.in AC 18 ms 456 KB
1
01_small_02.in AC 16 ms 560 KB
1
01_small_03.in AC 17 ms 660 KB
1
01_small_04.in AC 13 ms 508 KB
1
01_small_05.in AC 17 ms 612 KB
1
01_small_06.in AC 12 ms 588 KB
1
01_small_07.in AC 17 ms 432 KB
1
01_small_08.in AC 14 ms 664 KB
1
01_small_09.in AC 18 ms 636 KB
1
01_small_10.in AC 17 ms 608 KB
1
02_random_01.in AC 67 ms 2116 KB
1
02_random_02.in AC 121 ms 3488 KB
1
02_random_03.in AC 405 ms 8820 KB
1
02_random_04.in AC 79 ms 2224 KB
1
02_random_05.in AC 135 ms 3540 KB
1
02_random_06.in AC 392 ms 9352 KB
1
02_random_07.in AC 281 ms 7184 KB
1
02_random_08.in AC 262 ms 6776 KB
1
02_random_09.in AC 259 ms 6212 KB
1
02_random_10.in AC 287 ms 6740 KB
1
02_random_11.in AC 390 ms 9364 KB
1
02_random_12.in AC 325 ms 7428 KB
1
02_random_13.in AC 295 ms 7748 KB
1
02_random_14.in AC 301 ms 7444 KB
1
02_random_15.in AC 158 ms 4480 KB
1
02_random_16.in AC 187 ms 3996 KB
1
02_random_17.in AC 21 ms 748 KB
1
02_random_18.in AC 343 ms 8524 KB
1
02_random_19.in AC 331 ms 8172 KB
1
02_random_20.in AC 307 ms 5012 KB
1
02_random_21.in AC 202 ms 5568 KB
1
02_random_22.in AC 217 ms 5576 KB
1
02_random_23.in AC 59 ms 1512 KB
1
02_random_24.in AC 202 ms 4860 KB
1
02_random_25.in AC 235 ms 6576 KB
1
02_random_26.in AC 215 ms 5512 KB
1
02_random_27.in AC 223 ms 5536 KB
1
02_random_28.in AC 312 ms 7812 KB
1
02_random_29.in AC 207 ms 5104 KB
1
02_random_30.in AC 90 ms 2540 KB
1
03_large_01.in AC 414 ms 9992 KB
1
03_large_02.in AC 408 ms 9992 KB
1
03_large_03.in AC 402 ms 9868 KB
1
03_large_04.in AC 405 ms 9884 KB
1
03_large_05.in AC 409 ms 9896 KB
1
03_large_06.in AC 406 ms 9932 KB
1
03_large_07.in AC 400 ms 9948 KB
1
03_large_08.in AC 405 ms 9952 KB
1
03_large_09.in AC 400 ms 9972 KB
1
03_large_10.in AC 404 ms 9980 KB
1