Submission #00335

ソースコード

?
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
struct T;
#define null ((T*)NULL)
struct T {
int v;
int pri;
int cnt;
int lazy;
T *l,*r;
T(){}
T(int v,int p=rand()):v(v),pri(p),cnt(1),lazy(0),l(null),r(null){}
};
int hogeS=0;
const int SIZE=222222*3;
T hoge[SIZE];
inline T* New(int v)
{
if( hogeS >= SIZE ) for(;;);
hoge[hogeS] = T(v);
return &hoge[hogeS++];
}
inline int count(T* t){ return !t?0:t->cnt; }
inline void push(T* t)
{
if( !t ) return;
if( t -> lazy ) {
t->v += t->lazy;
if(t->l) t->l->lazy += t->lazy;
if(t->r) t->r->lazy += t->lazy;
t->lazy = 0;
}
}
inline T* update(T* t)
{
if(!t)return t;
push(t);
t->cnt = count(t->l)+count(t->r)+1;
return t;
}
void split(T* t,int v,T *&l,T *&r)
{
push(t);
if(!t) {
l=r=null;
} else if( t->v <= v ) {
split(t->r,v,t->r,r);
l = update(t);
} else {
split(t->l,v,l,t->l);
r = update(t);
}
}
T* insert(T* t,T* s)
{
push(t);
push(s);
if(!t) return s;
if(!s) return s;
if( t->pri < s->pri ) {
split(t,s->v,s->l,s->r);
return update(s);
}
if( t->v < s->v ) t->r = insert(t->r,s);
else t->l = insert(t->l,s);
return update(t);
}
T* merge(T* l,T* r)
{
T* t;
push(l);
push(r);
if(!l||!r)t=(!l?r:l);
else if(l->pri < r->pri){
r->l = merge(l,r->l);
t = r;
} else {
l->r = merge(l->r,r);
t = l;
}
return update(t);
}
T* erase(T* t,int k)
{
if( !t ) return t;
push(t);
//printf("[%d,%d] k:%d\n",t->v,t->cnt,k);
if(t->v == k ) {
T* ret = merge(t->l,t->r);
return ret;
}
if( t->v > k ) {
t->l = erase(t->l,k);
} else {
t->r = erase(t->r,k);
}
return update(t);
}
int solve(T* t,int k)
{
if( !t ) return 0;
if (t->v >= k) {
return solve(t->l, k) + count(t->r) + 1;
} else {
return solve(t->r, k);
}
}
int n, q;
T* t = null;
int p[111111];
int main(void) {
scanf("%d%d", &n, &q);
/*
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(1));
t = insert(t, New(3));
t = insert(t, New(2));
t = insert(t, New(6));
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(2));
t = insert(t, New(4));
t = insert(t, New(5));
t = insert(t, New(2));
t = insert(t, New(2));
puts("a");
printf("%d\n", solve(t, 1));
printf("%d\n", solve(t, 2));
printf("%d\n", solve(t, 3));
printf("%d\n", solve(t, 4));
printf("%d\n", solve(t, 5));
printf("%d\n", solve(t, 6));
t = erase(t, 2);
t = erase(t, 4);
t = erase(t, 2);
t = erase(t, 2);
t = erase(t, 6);
printf("%d\n", solve(t, 1));
printf("%d\n", solve(t, 2));
printf("%d\n", solve(t, 3));
printf("%d\n", solve(t, 4));
printf("%d\n", solve(t, 5));
printf("%d\n", solve(t, 6));
puts("a");
//*/
t = null;
for (int i = 0; i < q; i++) {
int a, b, c; scanf("%d%d", &a, &b);
if (a == 1) {
scanf("%d", &c);
if (p[c] == 0) {
t = insert(t, New(b));
p[c] = b;
} else if (p[c] > b) {
t = erase(t, p[c]);
t = insert(t, New(b));
p[c] = b;
}
} else {
printf("%d\n", solve(t, b));
fflush(stdout);
}
}
return 0;
}

ステータス

項目 データ
問題 0002 - ghoststudents
ユーザー名 💩
投稿日時 2017-07-07 22:49:55
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 3443 Byte
最大実行時間 30 ms
最大メモリ使用量 1076 KB

セット

セット 得点 Cases
1 ALL 0 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_01.in AC 18 ms 480 KB
1
01_small_01.in AC 18 ms 712 KB
1
01_small_02.in AC 13 ms 560 KB
1
01_small_03.in AC 14 ms 532 KB
1
01_small_04.in AC 16 ms 636 KB
1
01_small_05.in AC 19 ms 480 KB
1
01_small_06.in AC 17 ms 580 KB
1
01_small_07.in WA 15 ms 552 KB
1
01_small_08.in AC 17 ms 652 KB
1
01_small_09.in AC 16 ms 624 KB
1
01_small_10.in WA 15 ms 592 KB
1
02_random_01.in WA 18 ms 828 KB
1
02_random_02.in WA 24 ms 828 KB
1
02_random_03.in WA 29 ms 868 KB
1
02_random_04.in WA 21 ms 828 KB
1
02_random_05.in WA 19 ms 740 KB
1
02_random_06.in WA 27 ms 856 KB
1
02_random_07.in WA 24 ms 920 KB
1
02_random_08.in WA 30 ms 792 KB
1
02_random_09.in WA 22 ms 724 KB
1
02_random_10.in WA 19 ms 688 KB
1
02_random_11.in WA 21 ms 876 KB
1
02_random_12.in WA 22 ms 796 KB
1
02_random_13.in WA 20 ms 876 KB
1
02_random_14.in WA 24 ms 724 KB
1
02_random_15.in WA 19 ms 908 KB
1
02_random_16.in WA 21 ms 656 KB
1
02_random_17.in WA 20 ms 692 KB
1
02_random_18.in WA 22 ms 952 KB
1
02_random_19.in WA 21 ms 808 KB
1
02_random_20.in WA 19 ms 460 KB
1
02_random_21.in WA 21 ms 648 KB
1
02_random_22.in WA 24 ms 804 KB
1
02_random_23.in WA 17 ms 724 KB
1
02_random_24.in WA 19 ms 628 KB
1
02_random_25.in WA 18 ms 744 KB
1
02_random_26.in WA 22 ms 684 KB
1
02_random_27.in WA 19 ms 696 KB
1
02_random_28.in WA 17 ms 676 KB
1
02_random_29.in WA 21 ms 664 KB
1
02_random_30.in WA 18 ms 752 KB
1
03_large_01.in WA 20 ms 780 KB
1
03_large_02.in WA 22 ms 868 KB
1
03_large_03.in WA 24 ms 968 KB
1
03_large_04.in WA 20 ms 792 KB
1
03_large_05.in WA 29 ms 1076 KB
1
03_large_06.in WA 25 ms 1032 KB
1
03_large_07.in WA 23 ms 868 KB
1
03_large_08.in WA 26 ms 868 KB
1
03_large_09.in WA 23 ms 700 KB
1
03_large_10.in WA 23 ms 772 KB
1