Submission #42337

ソースコード

?
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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef pair<char,int>Char_Int;
const Char_Int INF=Char_Int('z',1<<30);
struct BIT{
int data[200005];
int n;
BIT(int n):n(n)
{
for(int i=1;i<=n;i++){
data[i]=(i&-i);
}
return;
}
void add(int index,int x)
{
index++;
while(index<=n){
data[index]+=x;
index+=(index&-index);
}
return;
}
int sum(int index)
{
int s=0;
index++;
while(index>0){
s+=data[index];
index-=(index&-index);
}
return(s);
}
};
struct SegmentTree{
Char_Int data[555555];
int n;
SegmentTree(int a)
{
n=1;
while(n<a){
n*=2;
}
for(int i=0;i<=n;i++){
data[i]=INF;
}
}
void update(int index,Char_Int x)
{
index+=n-1;
data[index]=x;
while(index>0){
index=(index-1)/2;
data[index]=min(data[index*2+1],data[index*2+2]);
}
return;
}
Char_Int query(int a,int b,int left,int right,int node)
{
if(a<=left&&right<=b){
return(data[node]);
}
if(right<a||b<left){
return(INF);
}
Char_Int vleft=query(a,b,left,(left+right)/2,node*2+1);
Char_Int vright=query(a,b,(left+right)/2+1,right,node*2+2);
return(min(vleft,vright));
}
Char_Int find(int a,int b)
{
return(query(a,b,0,n-1,0));
}
};
int main()
{
string str;
int k;
cin>>str>>k;
BIT bit(str.size());
SegmentTree seg(str.size());
for(int i=0;i<str.size();i++){
seg.update(i,Char_Int(str[i],i));
}
for(int i=0;i<str.size();i++){
int left=0;
int right=str.size();
int mid=(left+right)/2;
while(left+1<right){
if(bit.sum(mid)-1<=k){
left=mid;
}else{
right=mid;
}
mid=(left+right)/2;
}
Char_Int change=seg.find(0,left);
cout<<change.first;
k-=bit.sum(change.second)-1;
bit.add(change.second,-1);
seg.update(change.second,INF);
}
cout<<endl;
return(0);
}

ステータス

項目 データ
問題 0963 - 人気のユーザ名
ユーザー名 ei1630
投稿日時 2018-08-31 09:11:11
言語 C++11
状態 Accepted
得点 14
ソースコード長 2131 Byte
最大実行時間 109 ms
最大メモリ使用量 8540 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 26 ms 5212 KB
1
in2.txt AC 22 ms 5396 KB
1
in3.txt AC 24 ms 7244 KB
1
in4.txt AC 24 ms 7508 KB
1
in5.txt AC 25 ms 7492 KB
1
in6.txt AC 21 ms 7348 KB
1
in7.txt AC 22 ms 7464 KB
1
in8.txt AC 22 ms 7448 KB
1
in9.txt AC 16 ms 7424 KB
1
in10.txt AC 24 ms 5732 KB
1
in11.txt AC 18 ms 5076 KB
1
in12.txt AC 17 ms 4844 KB
1
in13.txt AC 25 ms 4884 KB
1
in14.txt AC 21 ms 4904 KB
1
in15.txt AC 26 ms 5140 KB
1
in16.txt AC 26 ms 5432 KB
1
in17.txt AC 66 ms 5632 KB
1
in18.txt AC 65 ms 6280 KB
1
in19.txt AC 69 ms 6412 KB
1
in20.txt AC 65 ms 6276 KB
1
in21.txt AC 88 ms 6948 KB
1
in22.txt AC 109 ms 7260 KB
1
in23.txt AC 101 ms 7568 KB
1
in24.txt AC 99 ms 8008 KB
1
in25.txt AC 25 ms 7024 KB
1
in26.txt AC 19 ms 6948 KB
1
in27.txt AC 21 ms 7056 KB
1
in28.txt AC 25 ms 7032 KB
1
in29.txt AC 27 ms 7016 KB
1
in30.txt AC 19 ms 7308 KB
1
in31.txt AC 70 ms 7920 KB
1
in32.txt AC 70 ms 8540 KB
1