cf C. Knight Tournament

http://codeforces.com/contest/357/problem/C

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 300010
using namespace std; int n,m;
int l1,r1,x1;
struct node
{
int l,r;
int cover;
}tree[maxn*];
int x[maxn]; void build(int i,int l,int r)
{
tree[i].l=l;tree[i].r=r;
tree[i].cover=;
if(l==r) return ;
int mid=(l+r)>>;
build(i<<,l,mid);
build(i<<|,mid+,r);
}
void down(int i)
{
if(tree[i].l==tree[i].r) return ;
if(tree[i].cover>)
{
if(tree[i<<].cover==)
tree[i<<].cover=tree[i].cover;
if(tree[i<<|].cover==)
tree[i<<|].cover=tree[i].cover;
tree[i].cover=-;
}
}
void update(int i,int l,int r,int co)
{
if(tree[i].l==l&&tree[i].r==r)
{
if(tree[i].cover==)
{
tree[i].cover=co;
}
return ;
}
down(i);
int mid=(tree[i].l+tree[i].r)>>;
if(r<=mid)
{
update(i<<,l,r,co);
}
else if(l>mid)
{
update(i<<|,l,r,co);
}
else
{
update(i<<,l,mid,co);
update(i<<|,mid+,r,co);
}
} void search1(int i)
{
if(tree[i].l==tree[i].r)
{
x[tree[i].l]=tree[i].cover;
return;
}
down(i);
search1(i<<);
search1(i<<|);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,,n);
memset(x,,sizeof(x));
for(int i=; i<=m; i++)
{
scanf("%d%d%d",&l1,&r1,&x1);
if(l1==x1){
update(,l1+,r1,x1);
}
else if(r1==x1)
{
update(,l1,r1-,x1);
}
else
{
update(,l1,x1-,x1);
update(,x1+,r1,x1);
}
}
search1();
for(int i=; i<=n; i++)
{
if(i==)
printf("%d",x[i]);
else
printf(" %d",x[i]);
}
printf("\n");
}
return ;
}
上一篇:EXT Grid celleditor列编辑,动态控制某一单元格只读


下一篇:时间同步装置(时间同步系统)到底有什么作用?