Submission #52500

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
struct Moji {
char m;
int id;
Moji ( char a = 'z'+1, int b = 0 ) {
m = a;
id = b;
}
};
template<class T>
struct SegmentTree {
int size;
T nullValue;
vector<T> data;
SegmentTree ( int n, T defaultValue, T nullValue) {
for ( size = 1; size < n; size *= 2 );
data.resize( 2*size-1, defaultValue);
this->nullValue = nullValue;
}
T marge ( T a, T b ) {
if ( a.m == b.m ) {
if ( a.id < b.id ) {
return a;
}
return b;
}
if ( a.m < b.m ) {
return a;
}
return b;
}
void update ( int pos, T value ) {
pos += size-1;
data[pos] = value;
while ( pos > 0 ) {
pos = ( pos - 1 ) / 2;
data[pos] = marge( data[pos*2+1], data[pos*2+2] );
}
}
T get ( int begin, int end, int pos=0, int left=0, int right=-1 ) {
if ( right == -1 ) right = size;
if ( right <= begin || end <= left ) return nullValue;
if ( begin <= left && right <= end ) return data[pos];
int next = ( left + right ) / 2;
return marge(get ( begin, end, pos*2+1, left, next ), get ( begin, end, pos*2+2, next, right ));
}
inline const T& operator [] ( int index ) const {
return data[index+size-1];
}
inline T& operator [] ( int index ) {
return data[index+size-1];
}
};
/*
#########################################################
# #
# ## ##### # # #### ##### # # ##### #### #
# # # # ## # # # # # # # # # #
# # -- # # # # # # ##### # ##### # # #
# # # # ## # # # # # # # # #
# ##### ##### # # #### ##### # # ##### #### #
# #
#########################################################
*/
struct BinaryIndexedTree {
vector<int> data;
int size;
BinaryIndexedTree ( int n ) {
this->size = n;
data.resize(n);
}
void add ( int pos, int value ) {
for ( int i = pos; i <= size; i += i & -i ) {
data[i] += value;
}
}
// [1, pos]
int getSum ( int pos ) {
int sum = 0;
for ( int i = pos; i > 0; i -= i & -i ) {
sum += data[i];
}
return sum;
}
const int operator [] ( int pos ) const {
int sum = 0;
for ( int i = pos; i > 0; i -= i & -i ) {
sum += data[i];
}
return sum;
}
int lowerBound ( int value ) {
if ( value <= 0 ) return 0;
int x = 0;
int i = 1;
while ( i*2 <= size ) i *= 2;
for ( ; i > 0; i /= 2 ) {
if ( x + i <= size && data[x+i] < value ) {
value -= data[x+i];
x += i;
}
}
return x+1;
}
};
signed main ( ) {
string s;
int k;
cin >> s >> k;
SegmentTree<Moji> seg(s.size()+5, Moji(), Moji());
BinaryIndexedTree bit(s.size()+5);
queue<char> que;
for ( int i = 1; i <= s.size(); i++ ) {
seg.update(i, Moji(s[i-1], i));
bit.add(i, 1);
}
for ( int i = 0; i < s.size() && k > 0; i++ ) {
int mx = bit.lowerBound(min((int)s.size(), k+1))+1;
Moji tar = seg.get(1, mx);
k -= bit[tar.id];
k++;
que.push(tar.m);
bit.add(tar.id, -1);
seg.update(tar.id, Moji());
}
for ( int i = 1; i <= s.size(); i++ ) {
if ( seg[i].m <= 'z' ) {
que.push(seg[i].m);
}
}
while ( !que.empty() ) {
cout << que.front();
que.pop();
}
puts("");
return 0;
}

ステータス

項目 データ
問題 0963 - 人気のユーザ名
ユーザー名 r1825
投稿日時 2019-08-08 09:25:14
言語 C++
状態 Accepted
得点 14
ソースコード長 4022 Byte
最大実行時間 105 ms
最大メモリ使用量 7040 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 21 ms 604 KB
1
in2.txt AC 19 ms 824 KB
1
in3.txt AC 14 ms 1648 KB
1
in4.txt AC 25 ms 1832 KB
1
in5.txt AC 22 ms 2056 KB
1
in6.txt AC 21 ms 2148 KB
1
in7.txt AC 27 ms 1992 KB
1
in8.txt AC 24 ms 1960 KB
1
in9.txt AC 19 ms 2060 KB
1
in10.txt AC 28 ms 440 KB
1
in11.txt AC 23 ms 540 KB
1
in12.txt AC 24 ms 636 KB
1
in13.txt AC 25 ms 608 KB
1
in14.txt AC 18 ms 580 KB
1
in15.txt AC 29 ms 548 KB
1
in16.txt AC 16 ms 512 KB
1
in17.txt AC 38 ms 3292 KB
1
in18.txt AC 34 ms 3412 KB
1
in19.txt AC 27 ms 3396 KB
1
in20.txt AC 50 ms 3740 KB
1
in21.txt AC 105 ms 6564 KB
1
in22.txt AC 47 ms 6764 KB
1
in23.txt AC 48 ms 6840 KB
1
in24.txt AC 48 ms 7040 KB
1
in25.txt AC 28 ms 1728 KB
1
in26.txt AC 26 ms 1820 KB
1
in27.txt AC 24 ms 1908 KB
1
in28.txt AC 29 ms 1732 KB
1
in29.txt AC 30 ms 1824 KB
1
in30.txt AC 28 ms 1748 KB
1
in31.txt AC 40 ms 6708 KB
1
in32.txt AC 30 ms 4608 KB
1