【Codeforces Round 364 (Div 2)B】【简单讨论】Cells Not Under Attack 行列炮台覆盖不被攻击格子数

本文主要是介绍【Codeforces Round 364 (Div 2)B】【简单讨论】Cells Not Under Attack 行列炮台覆盖不被攻击格子数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

B. Cells Not Under Attack
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 arenot 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 0001 ≤ 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 3
1 1
3 1
2 2
output
4 2 0 
input
5 2
1 5
5 1
output
16 9 
input
100000 1
300 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.


#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int n, m;
bool line[N], list[N];
int main()
{while (~scanf("%d%d", &n, &m)){for (int i = 1; i <= n; ++i)line[i] = list[i] = 0;int linenum = n;int listnum = n;LL ans = (LL)n*n;for (int i = 1; i <= m; ++i){int y, x;scanf("%d%d", &y, &x);if (line[y] && list[x]);else if (line[y]){ans -= linenum;list[x] = 1;--listnum;}else if (list[x]){ans -= listnum;line[y] = 1;--linenum;}else{line[y] = list[x] = 1;ans -= linenum + listnum - 1;--linenum;--listnum;}printf("%lld ", ans);}puts("");}return 0;
}
/*
【题意】
n*n(1e5*1e5)的棋盘,我们要放炮台(m个),每个炮台可以攻击到同行或同列的所有格子。
问你每次放炮台之后还有多少个格子是不被攻击到的。【类型】
简单讨论【分析】
我们对哪行、哪些被炮台攻击到了做标记。
如果放的棋子,行列都被攻击到了,答案不变
如果只有行被攻击到了,那么答案-=剩余行数,列标记生效。【时间复杂度&&优化】
O(n+m)*/


这篇关于【Codeforces Round 364 (Div 2)B】【简单讨论】Cells Not Under Attack 行列炮台覆盖不被攻击格子数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610356

相关文章

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回(flashback)功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回(flashb

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

web网络安全之跨站脚本攻击(XSS)详解

《web网络安全之跨站脚本攻击(XSS)详解》:本文主要介绍web网络安全之跨站脚本攻击(XSS)的相关资料,跨站脚本攻击XSS是一种常见的Web安全漏洞,攻击者通过注入恶意脚本诱使用户执行,可能... 目录前言XSS 的类型1. 存储型 XSS(Stored XSS)示例:危害:2. 反射型 XSS(Re

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下:需要在