PATULJCI - Snow White and the N dwarfs

Snow White and the N dwarfs live in the forest. While the dwarfs mine away Snow White hangs around social networks.

Each morning the dwarfs form a long line and go whistling away to the mine. Snow White runs around them and snaps pictures to upload onto her favorite social network.

When dwarfs enter the mine, Snow White goes back to their house and goes through the pictures, selecting pretty ones. Each dwarf has a colored cap, and there are C different colors. A picture is pretty if more than half caps on it are of the same color. In other words, if there are K dwarfs on the picture, it is pretty if strictly more than K / 2 dwarfs have same colored caps.

Write a program that will check for a set of M pictures if they are pretty, and what color is dominating if they are.


First line contains two integers N and C (3 ≤ N ≤ 300000, 1 ≤ C ≤ 100000) number of dwarfs and number of colors.

Second line contains N integers between 1 and C (inclusive), colors of dwarves hats, ordered the way they formed the line that morning.

Third line contains M (1 ≤ M ≤ 100000), number of pictures.

Next M lines contain two integers A and B (1 ≤ A ≤ B ≤ N). Each line describes one picture. On it there are all dwarves starting from A-th all the way to the B-th.


Output M lines. For each picture output “no” if Snow White doesn't think the picture is pretty, and “yes X”, where X is the color dominating on the picture, if she does.


10 3
1 2 1 2 1 2 3 2 3 3
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

yes 1
yes 1
yes 2
yes 3

Được gửi lên bởi:Luka Kalinovcic
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:COCI 2009/2010 Contest #3

hide comments
2021-05-27 18:02:52
Tham khảo:
2019-02-21 06:23:03
MO k tle ...
2018-11-09 11:30:13
Mo's TLE nhỉ :3 ?
2015-11-22 05:31:01
mãi mới ac. bài này random ;-;
2015-11-15 04:18:34
tham khảo nè:
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.