MIS = lambda: map(int,input().split())
def compress(L):
L = list(L)
d = {}
for i, x in enumerate(sorted(L)): d[x] = i
return list(map(d.__getitem__, L))
class Fenwick:
def __init__(_, size): _.arr = [0]*size
def add(_, i, val):
while i < len(_.arr): _.arr[i] += val; i |= i+1
def getsum(_, i):
res = 0
while i >= 0: res+= _.arr[i]; i = (i&(i+1))-1
return res
def intersum(_, i, j): return _.getsum(j) - _.getsum(i-1)
n, k = MIS()
orig = list(MIS())
L = compress(orig)
F = Fenwick(n)
pos = []
for i, x in enumerate(L):
pos.append(i - min(k, F.intersum(x+1, n-1)))
F.add(x, 1)
# TODO optimize...
L = []
for i in range(n): L.insert(pos[i], orig[i])
print(*L)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
18244 KB |
Output is correct |
| 2 |
Correct |
35 ms |
18224 KB |
Output is correct |
| 3 |
Correct |
35 ms |
18160 KB |
Output is correct |
| 4 |
Correct |
36 ms |
18176 KB |
Output is correct |
| 5 |
Correct |
43 ms |
18152 KB |
Output is correct |
| 6 |
Correct |
46 ms |
18236 KB |
Output is correct |
| 7 |
Correct |
35 ms |
18212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
23252 KB |
Output is correct |
| 2 |
Correct |
60 ms |
19324 KB |
Output is correct |
| 3 |
Correct |
52 ms |
19008 KB |
Output is correct |
| 4 |
Correct |
75 ms |
22744 KB |
Output is correct |
| 5 |
Correct |
80 ms |
22688 KB |
Output is correct |
| 6 |
Correct |
89 ms |
22792 KB |
Output is correct |
| 7 |
Correct |
79 ms |
22772 KB |
Output is correct |
| 8 |
Correct |
81 ms |
22604 KB |
Output is correct |
| 9 |
Correct |
107 ms |
22904 KB |
Output is correct |
| 10 |
Correct |
74 ms |
22848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
800 ms |
37000 KB |
Output is correct |
| 2 |
Correct |
195 ms |
36480 KB |
Output is correct |
| 3 |
Correct |
460 ms |
36740 KB |
Output is correct |
| 4 |
Correct |
848 ms |
36428 KB |
Output is correct |
| 5 |
Correct |
678 ms |
36456 KB |
Output is correct |
| 6 |
Correct |
141 ms |
30212 KB |
Output is correct |
| 7 |
Correct |
795 ms |
36472 KB |
Output is correct |
| 8 |
Correct |
235 ms |
36492 KB |
Output is correct |
| 9 |
Correct |
208 ms |
36504 KB |
Output is correct |
| 10 |
Correct |
486 ms |
37184 KB |
Output is correct |
| 11 |
Correct |
233 ms |
37020 KB |
Output is correct |
| 12 |
Correct |
457 ms |
36144 KB |
Output is correct |
| 13 |
Correct |
682 ms |
36976 KB |
Output is correct |
| 14 |
Correct |
187 ms |
37040 KB |
Output is correct |
| 15 |
Correct |
551 ms |
37040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
35332 KB |
Output is correct |
| 2 |
Correct |
209 ms |
35328 KB |
Output is correct |
| 3 |
Correct |
476 ms |
33104 KB |
Output is correct |
| 4 |
Correct |
500 ms |
35200 KB |
Output is correct |
| 5 |
Correct |
899 ms |
35228 KB |
Output is correct |
| 6 |
Correct |
225 ms |
35256 KB |
Output is correct |
| 7 |
Correct |
865 ms |
35276 KB |
Output is correct |
| 8 |
Correct |
139 ms |
28468 KB |
Output is correct |
| 9 |
Correct |
709 ms |
35264 KB |
Output is correct |
| 10 |
Correct |
515 ms |
35304 KB |
Output is correct |
| 11 |
Correct |
815 ms |
35320 KB |
Output is correct |
| 12 |
Correct |
186 ms |
35264 KB |
Output is correct |
| 13 |
Correct |
691 ms |
35220 KB |
Output is correct |
| 14 |
Correct |
493 ms |
33804 KB |
Output is correct |
| 15 |
Correct |
185 ms |
35288 KB |
Output is correct |
