Submission #42196

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 300005;
const int SIZE = 530005;
int n;
P seg[SIZE];
int bit[SIZE]={};
int sel[200005]={};
//seg tree
void init();
void updata(int i, int x);
P find(P a, int node, int left, int right);
//BIT
void add(int i, int x);
int sum(int i);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k, m;
string buff, ans;
cin >> buff >> k;
if(m == 1) cout << buff << endl;
else if(m == 2){
if(k == 0) cout << buff << endl;
else{
cout << min(buff[0], buff[1]) << max(buff[0], buff[1]) << endl;
}
} else{
n = m = buff.size();
init();
for(int i=0;i<buff.size();i++){
updata(i, (int)buff[i]-'a');
}
/*
for(int i=0;i<buff.size();i++){
cout << seg[i+n].first << ' ';
}
cout << endl;
*/
//cout << n << endl;
//cout << find(P(1, 5), 0, 0, n).second << endl;
int count=0;
int index = k;
//if(index > m) index = m;
while(k > 0){
if(index > (m-1)) index = m-1;
P ch = find(P(0, index), 0, 0, n-1); //1 ~ K+1!!!!!!!!!!!!
if(ch.first == INF) break;
//cout << ch.second << endl;
ans += (char)ch.first+'a';
count++;
k-=(ch.second+1)-sum(ch.second+1)-1;
add(ch.second+1, 1);
sel[ch.second] = 1;
updata(ch.second, INF);
if(k <= 0 || count == m || ans.size() == buff.size()) break;
if(k >= (m-1)) index = m-1;
else{
int left=1 ,right = m, judge = k;
for(int j=0;j<20 && left < right;j++){
int midle = (left+right)/2;
int result = midle-sum(midle)-1;
if(result < judge) left = midle+1;
else if(result > judge) right = midle-1; //midle-1 ?
else {
left = midle;
break;
}
}
index = left-1;
}
}
for(int i=0;i<buff.size();i++){
if(sel[i] == 0) ans += buff[i];
}
cout << ans << endl;
}
return 0;
}
//seg tree
void init()
{
int l=1;
while(l < n){
l<<=1;
}
n = l;
for(int i=0;i<=2*n;i++) seg[i] = P(INF, INF);
return;
}
void updata(int i, int x)
{
i += n-1;
seg[i] = P(x, i-(n-1));
while(i > 0){
i = (i-1)/2;
seg[i] = min(seg[i*2+1], seg[i*2+2]);
}
return;
}
P find(P a, int node, int left, int right)
{
if(right < a.first || left > a.second) return(P(INF, INF));
if(a.first <= left && a.second >= right) return(seg[node]);
int midle = (left+right) / 2;
P cost1 = find(a, node*2+1, left, midle);
P cost2 = find(a, node*2+2, midle+1, right);
return(min(cost1, cost2));
}
//BIT
void add(int i, int x)
{
if(i == 0) return;
while(i < SIZE){
bit[i] += x;
i += i&(-i);
}
return;
}
int sum(int i)
{
if(i == 0) return 0;
int s=0;
while(i > 0){
s += bit[i];
i -= i&(-i);
}
return s;
}

ステータス

項目 データ
問題 0963 - 人気のユーザ名
ユーザー名 ei1612
投稿日時 2018-08-29 10:49:20
言語 C++17
状態 Accepted
得点 14
ソースコード長 3011 Byte
最大実行時間 70 ms
最大メモリ使用量 8372 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 21 ms 2652 KB
1
in2.txt AC 21 ms 2900 KB
1
in3.txt AC 18 ms 3808 KB
1
in4.txt AC 19 ms 4204 KB
1
in5.txt AC 22 ms 3988 KB
1
in6.txt AC 22 ms 4028 KB
1
in7.txt AC 24 ms 4068 KB
1
in8.txt AC 18 ms 4108 KB
1
in9.txt AC 17 ms 4144 KB
1
in10.txt AC 19 ms 2688 KB
1
in11.txt AC 15 ms 2476 KB
1
in12.txt AC 24 ms 2520 KB
1
in13.txt AC 27 ms 2560 KB
1
in14.txt AC 17 ms 2600 KB
1
in15.txt AC 18 ms 2640 KB
1
in16.txt AC 21 ms 2724 KB
1
in17.txt AC 28 ms 5188 KB
1
in18.txt AC 25 ms 5280 KB
1
in19.txt AC 26 ms 5368 KB
1
in20.txt AC 38 ms 6140 KB
1
in21.txt AC 70 ms 8036 KB
1
in22.txt AC 42 ms 6872 KB
1
in23.txt AC 42 ms 7144 KB
1
in24.txt AC 40 ms 8100 KB
1
in25.txt AC 22 ms 3884 KB
1
in26.txt AC 19 ms 3924 KB
1
in27.txt AC 18 ms 3956 KB
1
in28.txt AC 20 ms 3988 KB
1
in29.txt AC 22 ms 4028 KB
1
in30.txt AC 16 ms 3848 KB
1
in31.txt AC 41 ms 8372 KB
1
in32.txt AC 35 ms 7332 KB
1