Submission #19868299


Source Code Expand

Copy
n, k = gets.chomp.split(' ').map(&:to_i)
p    = gets.chomp.split(' ').map(&:to_i)

max = []
min = []
k.times do |i|
  until max.empty?
    break if max.last[0] > p[i]

    max.pop
  end
  until min.empty?
    break if min.last[0] < p[i]

    min.pop
  end
  max << [p[i], i]
  min << [p[i], i]
end

ans = 1
cnt = min.size == k ? 1 : 0
k.upto(n - 1) do |i|
  mi = [10 ** 18, 10 ** 18]
  max.shift if i - max.first[1] >= k
  mi = min.shift if i - min.first[1] >= k
  until max.empty?
    break if max.last[0] > p[i]

    max.pop
  end
  until min.empty?
    break if min.last[0] < p[i]

    min.pop
  end
  max << [p[i], i]
  min << [p[i], i]
  cnt += 1 if min.size == k
  unless mi[1] != 10 ** 18 && max.first[1] == i
    ans += 1 if min.size != k || cnt <= 1
  end
end

puts ans

Submission Info

Submission Time
Task B - Sorting a Segment
User coco18000
Language Ruby (2.7.1)
Score 700
Code Size 822 Byte
Status AC
Exec Time 226 ms
Memory 41916 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 32
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 61 ms 14220 KB
01-02.txt AC 61 ms 14112 KB
01-03.txt AC 193 ms 28208 KB
01-04.txt AC 185 ms 33168 KB
01-05.txt AC 143 ms 25700 KB
01-06.txt AC 162 ms 31244 KB
01-07.txt AC 202 ms 33980 KB
01-08.txt AC 223 ms 34324 KB
01-09.txt AC 210 ms 34252 KB
01-10.txt AC 217 ms 34336 KB
01-11.txt AC 226 ms 34084 KB
01-12.txt AC 203 ms 34180 KB
01-13.txt AC 216 ms 34092 KB
01-14.txt AC 224 ms 34252 KB
01-15.txt AC 200 ms 34584 KB
01-16.txt AC 213 ms 34792 KB
01-17.txt AC 201 ms 34132 KB
01-18.txt AC 194 ms 35712 KB
01-19.txt AC 205 ms 35208 KB
01-20.txt AC 199 ms 35356 KB
01-21.txt AC 186 ms 40660 KB
01-22.txt AC 194 ms 34348 KB
01-23.txt AC 186 ms 36324 KB
01-24.txt AC 197 ms 35564 KB
01-25.txt AC 169 ms 41916 KB
01-26.txt AC 183 ms 41576 KB
01-27.txt AC 184 ms 34264 KB
01-28.txt AC 167 ms 41164 KB
01-29.txt AC 165 ms 41180 KB
sample-01.txt AC 58 ms 14104 KB
sample-02.txt AC 64 ms 14252 KB
sample-03.txt AC 58 ms 14180 KB