Submission #52636

ソースコード

?
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#define min(X, Y) ((X) < (Y) ? (X) : (Y))
using namespace std;
typedef long long ll;
template<typename Monoid>
struct SegmentTree {
using OP = function<Monoid(Monoid, Monoid)>;
vector<Monoid> tree;
int size;
const OP f; // bin' operation
const Monoid e; // neutral element
SegmentTree(int nmemb, const Monoid &e, const OP &f):
f(f),
e(e)
{
size = 1;
while (size < nmemb) {
size *= 2;
}
tree.assign(2 * size - 1, e);
}
void update(int k, Monoid dat) {
k += size - 1;
tree[k] = dat;
while(k > 0) {
k = (k - 1) / 2;
tree[k] = f(tree[2 * k + 1], tree[2 * k + 2]);
}
}
// [l, r)
Monoid query(int l, int r) {
l += size - 1;
r += size - 1;
Monoid d = e;
while (l < r) {
if (l % 2 == 0) {
d = f(d, tree[l]);
l++;
}
if (r % 2 == 0) {
r--;
d = f(d, tree[r]);
}
l = (l - 1) / 2;
r = (r - 1) / 2;
}
return d;
}
Monoid operator[] (const int k) {return query(k, k + 1);}
};
struct Character {
ll ch, idx;
Character(){}
Character(ll ch, ll idx):ch(ch), idx(idx){}
bool operator < (const Character &r) {
Character l(this->ch, this->idx);
if (l.ch < r.ch) return true;
else if (l.ch == r.ch && l.idx < r.idx) return true;
else return false;
}
};
int main() {
string ans;
string s;
ll k;
ll n;
cin >> s;
cin >> k;
n = s.size();
SegmentTree<Character> RMQ(n, Character(1ll << 60ll, 0),
[](auto l, auto r){return min(l, r);});
SegmentTree<ll> RSQ(n, 0,
[](auto l, auto r){ return l + r;});
// RSQ.update(n, 1ll << 40ll);
for (int i = 0; i < n; i++) {
RMQ.update(i, Character(s[i], i));
}
while (k > 0 && RSQ.query(0, n) < n) {
ll invalid, valid;
valid = 0;
invalid = n;
while (invalid - valid > 1) {
ll mid = (invalid + valid) / 2;
if (mid - RSQ.query(0, mid + 1) > k) {
invalid = mid;
}
else {
valid = mid;
}
}
Character x = RMQ.query(0, valid + 1);
ans += (char)x.ch;
RSQ.update(x.idx, 1);
RMQ.update(x.idx, Character(1ll << 60ll, 0));
k -= x.idx - RSQ.query(0, x.idx);
}
for (int i = 0; i < n; i++) {
if (!RSQ[i]) {
ans += s[i];
}
}
cout << ans << endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 24 ms 604 KB
1
in2.txt AC 24 ms 832 KB
1
in3.txt AC 27 ms 1800 KB
1
in4.txt AC 17 ms 1940 KB
1
in5.txt AC 24 ms 1916 KB
1
in6.txt AC 21 ms 2008 KB
1
in7.txt AC 23 ms 1976 KB
1
in8.txt AC 21 ms 1944 KB
1
in9.txt AC 18 ms 2040 KB
1
in10.txt AC 22 ms 568 KB
1
in11.txt AC 24 ms 408 KB
1
in12.txt AC 21 ms 512 KB
1
in13.txt AC 19 ms 480 KB
1
in14.txt AC 28 ms 576 KB
1
in15.txt AC 21 ms 544 KB
1
in16.txt AC 23 ms 648 KB
1
in17.txt AC 35 ms 7280 KB
1
in18.txt AC 37 ms 7308 KB
1
in19.txt AC 41 ms 7336 KB
1
in20.txt AC 58 ms 7464 KB
1
in21.txt AC 237 ms 14048 KB
1
in22.txt AC 69 ms 14164 KB
1
in23.txt AC 63 ms 14408 KB
1
in24.txt AC 69 ms 14528 KB
1
in25.txt AC 16 ms 1816 KB
1
in26.txt AC 31 ms 1776 KB
1
in27.txt AC 21 ms 1856 KB
1
in28.txt AC 18 ms 1644 KB
1
in29.txt AC 21 ms 1732 KB
1
in30.txt AC 19 ms 1648 KB
1
in31.txt AC 57 ms 14528 KB
1
in32.txt AC 53 ms 8344 KB
1