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

collectingstamps Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

collecting.html

JOI-kun likes to collect images and has collected many images. Recently, he has been collecting too many images and noticed, to his dismay, that his hard disk is running out of space. Unfortunately, he doesn't have enough savings to buy a new hard disk. It pains JOI-kun to delete any of the images he has painstakingly collected, so he has decided to use compression to minimize the space requirements of his image collection.

Each image consists of 2N rows and 2N columns of pixels for a total of 2N × 2N pixels. Each pixel has one of two colours: black or white.

JOI-kun has decided to compress his images with the following method:

  • If the pixels within an image consist entirely of pixels of the same colour, JOI-kun records the colour of the pixel. The compressed size of such an image is 1.
  • If the pixels within an image are not all of the same colour, then JOI-kun divides the image into four sub-images. For an image of size 2k × 2k, the centre of the image divides the image into four sub-images of size 2k-1 × 2k-1. The four sub-images are then compressed in the same manner. The compressed size of such an image is the sum of the compressed sizes of the four sub images + 1.

JOI-kun is unsure if this compression scheme is able to compress his images safely, so he decided to test this compression scheme before using it on all of his images. The testing is done in the following manner:

  • The test begins with an all-white image.
  • For i = 1, …, Q, an operation is performed using two integers Ti and Xi.

    • If Ti = 0, the colours of the pixels on the Xith row of the image are flipped. In other words, denoting a pixel on the ath row from the top and bth column from the left by (a, b), all pixels (Xi, b) for 1 ≤ b ≤ 2N are flipped.
    • If Ti = 1, the colours of the pixels on the Xith column of the image are flipped. In other words, all pixels (a, Xi) for 1 ≤ a ≤ 2N are flipped.

    When a pixel is flipped, it becomes black if it was initially white and white if it was initially black.

  • After each operation, the compressed size of the resulting image is recorded.

JOI-kun would like to test the compression scheme thoroughly with many operations, so he needs to be able to determine the compressed size of the image after each operation as quickly as possible.

Given the size of the image N and the Q operations JOI-kun will use to test the compression scheme, find the compressed size of the resulting image after each operation.

Input

Read from standard input.

  • On the first line, there are two integers, N and Q. This means that the image is of size 2N × 2N and Q operations will be performed on it.
  • On the ith line of the next Q lines, there are two integers, Ti and Xi (0 ≤ Ti ≤ 1 and 1 ≤ Xi ≤ 2N). If Ti = 0, this means that the ith operation flips the Xith row of the image, otherwise if Ti = 1, then the operation flips the Xith column of the image.

Output

Print to standard output. For each operation in the given order, print one integer on one line, representing the compressed size of the resulting image using JOI-kun's compression scheme.

Constraints

All test cases satisfy the following constraints.

  • 1 ≤ N ≤ 20.
  • 1 ≤ Q ≤ 2 000 000.

Subtasks

Subtask 1 (10 points):

The following constraints are satisfied.

  • N ≤ 6.
  • Q ≤ 128.

Subtask 2 (20 points):

The following constraints are satisfied.

  • N ≤ 10.
  • Q ≤ 2 048.

Subtask 3 (70 points):

No further constraints.

Sample Input

2 3
0 1
1 2
0 3

Sample Output

13
17
21

Explanation

In this test case, the state of the image before and after each of the Q = 3 operations is as follows:

Initial state: After operation 1: After operation 2: After operation 3:

→

→

→

collecting1.jpg

collecting3.jpg

collecting2.jpg

collecting4.jpg

Tags

JOI 2012/2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11073s256MBMinimum
22083s256MBMinimum
370133s256MBMinimum
4013s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o collectingstamps -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.