Submission #42173

ソースコード

?
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 09:33:42
言語 C++14
状態 Accepted
得点 14
ソースコード長 3011 Byte
最大実行時間 74 ms
最大メモリ使用量 8120 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 26 ms 2652 KB
1
in2.txt AC 23 ms 2900 KB
1
in3.txt AC 25 ms 3816 KB
1
in4.txt AC 24 ms 3956 KB
1
in5.txt AC 15 ms 3992 KB
1
in6.txt AC 21 ms 4032 KB
1
in7.txt AC 23 ms 4068 KB
1
in8.txt AC 20 ms 4108 KB
1
in9.txt AC 25 ms 4144 KB
1
in10.txt AC 18 ms 2436 KB
1
in11.txt AC 25 ms 2472 KB
1
in12.txt AC 16 ms 2516 KB
1
in13.txt AC 19 ms 2556 KB
1
in14.txt AC 19 ms 2596 KB
1
in15.txt AC 29 ms 2508 KB
1
in16.txt AC 16 ms 2460 KB
1
in17.txt AC 28 ms 5188 KB
1
in18.txt AC 27 ms 5276 KB
1
in19.txt AC 32 ms 5368 KB
1
in20.txt AC 31 ms 6140 KB
1
in21.txt AC 74 ms 8040 KB
1
in22.txt AC 43 ms 6748 KB
1
in23.txt AC 39 ms 7024 KB
1
in24.txt AC 35 ms 8112 KB
1
in25.txt AC 18 ms 3892 KB
1
in26.txt AC 17 ms 3804 KB
1
in27.txt AC 16 ms 3712 KB
1
in28.txt AC 23 ms 3740 KB
1
in29.txt AC 20 ms 3780 KB
1
in30.txt AC 14 ms 3724 KB
1
in31.txt AC 34 ms 8120 KB
1
in32.txt AC 38 ms 7340 KB
1