oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pigeonhole_ex Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

The pigeonhole principle states that given n+1 pigeons and n holes and that all pigeons are put into a hole, there must exist some hole that contains at least 2 pigeons

More generally, given p pigeons and n holes, there must exist some hole with ceil(p/n) pigeons

Guan is not convinced and wants to run a program to prove this

Each run of the program will simulate p pigeons leaving or entering holes. There will be h holes, numbered from 0 to h-1

Each pigeon has a number pi and will enter the hole (pi mod h) (i.e. pi%h) when it enters

Two pigeons may not have the same number

You are required to output whether there exist two pigeons in the same hole

Input

The first line of the input contains two integers, the number of operations n, and the number of holes h

For the next n lines, each line consists of an integer, either 0 or 1, 1 indicating entry and 0 indicating leaving of a pigeon. This integer is followed by another integer pi, indicating the number of the pigeon entering/leaving

No pigeon will leave before it has entered

Constraints

1<=pi<=1,000,000,000

Output

For each operation, output an integer on each line, the maximum number of pigeons in one hole

Subtasks

Subtask 1 (30%) n,h<=2000

Subtask 2 (70%) n,h<=2000000

Sample Testcase 1

Input

5 3
1 1
1 9001
0 9001
1 2
0 2
Output
1
2
1
1
1

Explanation

Pigeon 9001 shares the same hole as pigeon 1 (hole 1) (9001%3=1), but pigeon 2 does not share the same hole as pigeon 1, hence after operation two, there are two pigeons in the same hole, but not after operation three

Sample Testcase 2

Input

5 3
1 1
1 9001
1 2
0 2
0 9001
Output
1
2
2
2
1

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130101.5s32MBMinimum
270102.5s64MBMinimum
3021.5s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o pigeonhole_ex -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.