当前位置:网站首页>B. Applejack and Storages
B. Applejack and Storages
2022-08-09 21:55:00 【秦小咩】
B. Applejack and Storages
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This year in Equestria was a year of plenty, so Applejack has decided to build some new apple storages. According to the advice of the farm designers, she chose to build two storages with non-zero area: one in the shape of a square and another one in the shape of a rectangle (which possibly can be a square as well).
Applejack will build the storages using planks, she is going to spend exactly one plank on each side of the storage. She can get planks from her friend's company. Initially, the company storehouse has nn planks, Applejack knows their lengths. The company keeps working so it receives orders and orders the planks itself. Applejack's friend can provide her with information about each operation. For convenience, he will give her information according to the following format:
- ++ xx: the storehouse received a plank with length xx
- −− xx: one plank with length xx was removed from the storehouse (it is guaranteed that the storehouse had some planks with length xx).
Applejack is still unsure about when she is going to order the planks so she wants to know if she can order the planks to build rectangular and square storages out of them after every event at the storehouse. Applejack is busy collecting apples and she has completely no time to do the calculations so she asked you for help!
We remind you that all four sides of a square are equal, and a rectangle has two pairs of equal sides.
Input
The first line contains a single integer nn (1≤n≤1051≤n≤105): the initial amount of planks at the company's storehouse, the second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1051≤ai≤105): the lengths of the planks.
The third line contains a single integer qq (1≤q≤1051≤q≤105): the number of events in the company. Each of the next qq lines contains a description of the events in a given format: the type of the event (a symbol ++ or −−) is given first, then goes the integer xx (1≤x≤1051≤x≤105).
Output
After every event in the company, print "YES" if two storages of the required shape can be built from the planks of that company's set, and print "NO" otherwise. You can print each letter in any case (upper or lower).
Example
input
Copy
6 1 1 1 2 1 1 6 + 2 + 1 - 1 + 2 - 1 + 2
output
Copy
NO YES NO NO NO YES
Note
After the second event Applejack can build a rectangular storage using planks with lengths 11, 22, 11, 22 and a square storage using planks with lengths 11, 11, 11, 11.
After the sixth event Applejack can build a rectangular storage using planks with lengths 22, 22, 22, 22 and a square storage using planks with lengths 11, 11, 11, 11.
=========================================================================
开始做之前让我感到棘手的是2 4的次数会产生重复,后来发现根本没必要,直接统计2,4的次数即可,一个4会带来两个2,到时候直接扣除即可
即两个4可以,一个4,外加4个2也可以,之所以是4个就可以,是因为要扣除1一个4的影响。
不少题解动辄几百行数据结构来解这个题,感到不解的同时,也只能感叹一下本是用来方便问题解决的算法成了掣肘思维的绊脚石
# include<iostream>
# include<string.h>
# include<vector>
using namespace std;
int cnt[100000+10];
int two=0,four=0;
int main ()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
cnt[x]++;
if(cnt[x]%2==0)
two++;
if(cnt[x]%4==0)
four++;
}
int t;
cin>>t;
while(t--)
{
char ch;
int x;
cin>>ch>>x;
if(ch=='-')
{
cnt[x]--;
if(cnt[x]%2==1)
two--;
if(cnt[x]%4==3)
four--;
}
else
{
cnt[x]++;
if(cnt[x]%2==0)
two++;
if(cnt[x]%4==0)
four++;
}
if(four>=2||(four>=1&&two>=4))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
边栏推荐
- 重装系统后新建文本文档打不开怎么办
- 17-GuliMall 搭建虚拟域名访问环境
- Use convert_to_tensor in Tensorflow to specify the type of data
- 【EF】 更新条目时出错。有关详细信息,请参见内部异常。[通俗易懂]
- 国内手机厂商曾为它大打出手,如今它却最先垮台……
- 你的 Link Button 能让用户选择新页面打开吗?
- Synchronization lock synchronized traces the source
- Technology Sharing | How to Handle Header Cookies in Interface Automation Testing
- Quotefancy ,提供鼓舞人心语录的壁纸网站 - 倾城之链
- In-depth analysis of Apache EventMesh cloud-native distributed event-driven architecture
猜你喜欢
The kvm virtual machine cannot be started, NOT available, and the PV is larger than the partition
Five Star Holdings Wang Jianguo: Deepen the track with "plant spirit" and promote growth with "animal spirit"
Under the NVM node installation;The node environment variable configuration
[Microservice~Nacos] Configuration Center of Nacos
2022年中国第三方证券APP创新专题分析
JS Deobfuscation - AST Restoration Case
MySQL——JDBC
聊天尬死名场面,你遇到过吗?教你一键获取斗图表情包,晋升聊天达人
Basic JSON usage
关于ETL的两种架构(ETL架构和ELT架构)
随机推荐
金山云地震,震源在字节?
Several ways to draw timeline diagrams
注意力引导网络用于视网膜图像分割
NIO Cup 2022 Nioke Summer Multi-School Training Camp 7 CFGJ
TRUNCATE表之后空间未释放
Reinforcement Learning Weekly Issue 57: DL-DRL, FedDRL & Deep VULMAN
面试官:MySQL 中 update 更新,数据与原数据相同时会执行吗?大部分人答不上来!
Flask's routing (app.route) detailed
[Cloud Native] 4.2 DevOps Lectures
阿里云架构师金云龙:基于云XR平台的视觉计算应用部署
一文让你快速了解隐式类型转换【整型提升】!
json case
L3-2 Delete up to three characters (30 points)
Analyze the Add() method in Fragment management from the source code
leetcode brush questions diary Calculate the number of elements on the right that is less than the current element
Cesium渐变色3dtiles白模(视频)
random.normal() and random.truncated_normal() in TF
mysql multi-table left link query
【EF】 更新条目时出错。有关详细信息,请参见内部异常。[通俗易懂]
Quotefancy ,提供鼓舞人心语录的壁纸网站 - 倾城之链