cf701B Cells Not Under Attack

Vasya has the square chessboard of size n × n and m rooks. Initially the chessboard is empty. Vasya will consequently put the rooks on the board one after another.

The cell of the field is under rook‘s attack, if there is at least one rook located in the same row or in the same column with this cell. If there is a rook located in the cell, this cell is also under attack.

You are given the positions of the board where Vasya will put rooks. For each rook you have to determine the number of cells which are not under attack after Vasya puts it on the board.

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n2)) — the size of the board and the number of rooks.

Each of the next m lines contains integers xi and yi (1 ≤ xi, yi ≤ n) — the number of the row and the number of the column where Vasya will put the i-th rook. Vasya puts rooks on the board in the order they appear in the input. It is guaranteed that any cell will contain no more than one rook.

Output

Print m integer, the i-th of them should be equal to the number of cells that are not under attack after first i rooks are put.

Examples

input

3 31 13 12 2

output

4 2 0 

input

5 21 55 1

output

16 9 

input

100000 1300 400

output

9999800001 

Note

On the picture below show the state of the board after put each of the three rooks. The cells which painted with grey color is not under the attack.

记一下多少行多少列还是空着的然后乘起来

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<deque>
 9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define LL long long
13 #define inf 0x7ffffff
14 #define pa pair<int,int>
15 #define pi 3.1415926535897932384626433832795028841971
16 using namespace std;
17 inline LL read()
18 {
19     LL x=0,f=1;char ch=getchar();
20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
21     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
22     return x*f;
23 }
24 inline void write(LL a)
25 {
26     if (a<0){printf("-");a=-a;}
27     if (a>=10)write(a/10);
28     putchar(a%10+‘0‘);
29 }
30 inline void writeln(LL a){write(a);printf("\n");}
31 bool mrk1[100010],mrk2[100010];
32 int n,m;
33 LL col,row;
34 int main()
35 {
36     n=read();m=read();
37     col=n;row=n;
38     for (int i=1;i<=m;i++)
39     {
40         int x=read(),y=read();
41         if (!mrk1[x])mrk1[x]=1,col--;
42         if (!mrk2[y])mrk2[y]=1,row--;
43         cout<<col*row<<‘ ‘;
44     }
45 }

cf701B

时间: 07-21

cf701B Cells Not Under Attack的相关文章

Codeforces 701B. Cells Not Under Attack

Vasya has the square chessboard of size n?×?n and m rooks. Initially the chessboard is empty. Vasya will consequently put the rooks on the board one after another. The cell of the field is under rook's attack, if there is at least one rook located in

Codeforces Round #364 (Div. 2) ABCDE

A. Cards 题解: 目的是将n个数分成n/2个人,每个人2个,要求和一样,保证有解 排序一下再选取就行了 代码: #include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define ll long long typedef pair<int,int> P; const int INF=1

Codeforces Round #364 (Div. 2) - A B C

A - Cards /* 题意 : 有 n 张牌 ,每张牌都有一个数值 ,分给 n/2 个人 ,每个人手中的牌的数值加起来要相等, 一张牌只可分一个人. ( n 是偶数 ,且题目保证答案存在 ) 输出每个人手中的 牌的编号 . 解题 : 结构体存下牌的数值和编号,然后 sort 一下,从两边输出就好辣(因为答案保证存在). */ #include<cstdio> #include<cstring> #include<algorithm> #include<iost

单细胞文章分享:Molecular Diversity of Midbrain Development in Mouse, Human, and Stem Cells

Molecular Diversity of Midbrain Development in Mouse, Human, and Stem Cells 本文作者的官网:Ventral midbrain 顺便找到了:Download all the data and Python Notebooks from GitHub to reproduce the main figures. GitHub:linnarsson-lab/ipynb-lamanno2016 教程:scRNA-Seq Data

ZOJ 2587 Unique Attack 判断最小割是否唯一

很裸的判断最小割是否唯一.判断方法是先做一遍最大流求最小割,然后从源点和汇点分别遍历所有能够到达的点,看是否覆盖了所有的点,如果覆盖了所有的点,那就是唯一的,否则就是不唯一的. #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostr

C# 基于Aspose.Cells的数据导出到Excel

using Aspose.Cells; void WriteToExcel(string filePath, List<object[]> datas, string sheetName = "Sheet0") { try { Workbook workBook = new Workbook(); Worksheet sheet = workBook.Worksheets[0]; sheet.Name = sheetName; Aspose.Cells.Style styl

【树状数组区间修改单点查询】HDU 4031 Attack

http://acm.hdu.edu.cn/showproblem.php?pid=4031 [题意] 有一个长为n的长城,进行q次操作,d为防护罩的冷却时间,Attack表示区间a-b的墙将在1秒后受到攻击, 询问表示计算第a块墙受到攻击的次数,被防护罩抵消的不算 [思路] 总的攻击次数-防护罩抵消的次数 总的攻击次数可以树状数组维护 防护罩抵消的模拟 [AC] 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long l

dwr的A request has been denied as a potential CSRF attack.错误

虽然DWR是个很早就出现的Ajax框架,但一直都没去使用过,今天正好没事就看了一下并参照文档照做了个demo, 在其中碰到一个问题: 后台打印出错误信息:"严重: A request has been denied as a potential CSRF attack." 在网上google一把 之后,出现此错误的原因大都是说"请求被拒绝,可能存在csrf(cross-site request forgeries,跨站请求伪造)攻击. 页面URL可能被跨站了的服务所调用之类的

ASP.NET Padding Oracle Attack EXP

#!/usr/bin/perl## PadBuster v0.3 - Automated script for performing Padding Oracle attacks# Brian Holyfield - Gotham Digital Science ([email protected])## Credits to J.Rizzo and T.Duong for providing proof of concept web exploit# techniques and S.Vaud

GitHub_HeadersDownCells_标题view下拉子cells

标题view下拉子cells,可以自定义标题View.子cell的内容及数量,最近会继续优化 https://github.com/alwaysDB/HeadersDownCells.git 以下为部分代码 1 - (void)groupHeaderViewDidClickBtnGroupTitle:(BabySettingHeaderView *)groupHeaderView { 2 // [self.tableView reloadData]; 3 // DDLog(@"groupHead