Knight Tournament (set)
Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.
As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:
- There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.
- The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least li and at most ri have fought for the right to continue taking part in the tournament.
- After the i-th fight among all participants of the fight only one knight won — the knight number xi, he continued participating in the tournament. Other knights left the tournament.
- The winner of the last (the m-th) fight (the knight number xm) became the winner of the tournament.
You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.
Write the code that calculates for each knight, the name of the knight that beat him.
Input
The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — the number of knights and the number of fights. Each of the following m lines contains three integers li, ri, xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri) — the description of the i-th fight.
It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.
Output
Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.
题解:用set来模拟
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int a[1000005];
int main()
{
set<int>s;
set<int>::iterator it;
int n,m;
cin>>n>>m;
s.clear();
for(int t=1;t<=n;t++)
{
s.insert(t);
}
int l,r,x;
for (int t=1;t<=m;t++)
{
x=s.size();
scanf("%d%d%d",&l,&r,&x);
it=s.lower_bound(l);
int h;
while (it!=s.end() && *it<=r)
{
h=*it;
it++;
if (h!=x)
{
a[h]=x;
s.erase(h);
}
}
}
printf("%d",a[1]);
for(int t=2;t<=n;t++)
{
printf(" %d",a[t]);
}
return 0;
}
最新文章
- c# Using Settings under visual studio 2012
- IOS开发资料汇总
- 从github拉取项目到myeclipse本地
- ES6笔记(1) -- 环境配置支持
- asp.net Excel数据导入到数据库中
- qsort用法总结
- 尝试跑一跑Scut
- 12个非常有用的JavaScript小技巧
- DWZ在APS.NET WebForm中的使用(二)
- 百度百科Tooltip的实现--原生js的应用
- 选择语句--switch
- elasticSearch 2.3 delete-by-query plugin
- Android手机有的不显示Toast
- 20135323符运锦----LINUX第三次实践:程序破解
- AangularJS的表单验证
- 回看《例说FPGA》---DDR2控制器集成与读写测试
- python函数知识
- django中的 form 表单操作
- 加载样式js
- Android实现图片下载并保存SD卡