首页 > 代码库 > AC日记——校门外的树(增强版) 洛谷 P1276
AC日记——校门外的树(增强版) 洛谷 P1276
题目描述
校门外马路上本来从编号0到L,每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树,就连树苗也不放过(记 0 A B ,含A和B);幸运的是还有植树者每次从编号C到D 中凡是空穴(树被砍且还没种上树苗或树苗又被砍掉)的地方都补种上树苗(记 1 C D,含C和D);问最终校门外留下的树苗多少棵?植树者种上又被砍掉的树苗有多少棵?
输入输出格式
输入格式:
第一行L和N,表示校园外原来有L+1棵树,并有N次砍树或种树的操作。
以下N行,砍树或植树的标记和范围,每行3个整数。
L(1 <= L <= 10000)和 N(1 <= N <= 100)
输出格式:
共两行。第1行校门外留下的树苗数目,第2行种上又被拔掉的树苗数目。
输入输出样例
输入样例#1:
10 30 2 61 1 80 5 7
输出样例#1:
32
说明
【数据范围】
对于100%的数据0≤n,l≤10^9
思路:
线段树写蹦了,写了个模拟水过;
来,上代码:
#include <cstdio>using namespace std;int m,n,ai[10001],ans_=0,ans=0;bool if_[10001];int main(){ scanf("%d%d",&n,&m); int l,r,ty; for(int i=1;i<=m;i++) { scanf("%d%d%d",&ty,&l,&r); if(ty) { for(int j=l;j<=r;j++) { if(!ai[j]&&if_[j]) ai[j]++; } } else { for(int j=l;j<=r;j++) { if(if_[j]&&ai[j]) ans_++; if_[j]=true; ai[j]=0; } } } for(int i=0;i<=n;i++) { if(ai[i]) ans++; } printf("%d\n%d\n",ans,ans_); return 0;}
AC日记——校门外的树(增强版) 洛谷 P1276
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。