种种星球管理接收到的数目须求三个单位时间,每种星球管理接收到的数码须要一个单位时间

大sz的游戏

Time Limit: 50 Sec  Memory
Limit: 357 MB
Submit: 536  Solved: 143
[Submit][Status][Discuss]

大sz的游戏

Time Limit: 50 Sec  Memory
Limit: 357 MB
Submit: 536  Solved: 143
[Submit][Status][Discuss]

Description

大sz最近在玩一个由星球战争改编的十六日游。话说绝地武士当前共控制了N个星球。不过,西斯正在暗处悄悄地筹划他们的算账陈设。绝地评议会也感觉到了那件事。于是,筹划加派绝地武士到各星球幸免西斯的突袭。一个星星受到攻击之后,会急速文告到总营地。必要的年月越长的星球就须要越来越多绝地武士来防御。为了客观分配轻易的武士,大sz必要您帮他求出各种星球各需求有个别时间能够公告到总集散地。由于某种原因,N个星球排成一条直线,编号1至N。个中总营地建在一号星球上。每一种星球即使都以绝地武士调节的,可是上面居住的生物不自然同样,并且科学技术水准也不均等。第i个星球能收到并分析波长在[xi,
yi]中间的功率信号,并且也能够发出在那个距离的随机信号,可是不能够发出任何任何波长的频域信号。由于本事原因,各种星球只可以发能量信号到比本人编号小的距离不当先L的星辰。特别地,壮大的总集散地尚可任何波长的时域信号。各个星球管理接收到的数目必要贰个单位时间,传输时间能够忽略不计。

Description

大sz近日在玩多少个由星球战役改编的嬉戏。话说绝地武士当前共调控了N个星球。但是,西斯正值暗处悄悄地企图他们的复仇计划。绝地评议会也深感觉了那件事。于是,计划加派绝地武士到各星球幸免西斯的偷袭。二个星体受到攻击之后,会尽快布告到总集散地。供给的大运越长的星斗就必要更多绝地武士来防范。为了创制分配简单的斗士,大sz需求你帮他求出每种星球各供给多少日子能够通告到总营地。由于某种原因,N个星球排成一条直线,编号一至N。当中总基地建在一号星球上。每种星球纵然都以绝地武士调控的,可是地点居住的海洋生物不确定一样,并且科学技术程度也不一致。第i个星球能收到并分析波长在[xi,
yi]以内的确定性信号,并且也能够爆发在那么些间隔的复信号,但是不可能发出任何任何波长的复信号。由于才具原因,每种星球只好发时限信号到比自身编号小的相距不超越L的星球。特别地,强大的总集散地能够接过任何波长的非复信号。各样星球管理接收到的数码需求三个单位时间,传输时间足以忽略不计。

Input

首先行多少个正整数N、L。接下来N-一行,总共第i行李包裹蕴了多个正整数xi、yi、li,当中li表示第i个星球距离1号星球li,满意li严刻递增。

Input

先是行七个正整数N、L。接下来N-1行,总共第i行李包裹罗了四个正整数xi、yi、li,在那之中li表示第i个星球距离一号星球li,满足li严俊递增。

Output

共计N-1行,每行三个数分别表示贰到N号星球至少需求多少单位时间,总营地能够处理好数据,如若不或者传到总集散地则输出-壹。

Output

共计N-一行,每行2个数分别代表贰到N号星球至少须要某个单位时间,总集散地能够管理好数据,假如无法传到总基地则输出-一。

Sample Input

input1
3 1
1 2 1
2 3 2
input 2
3 3
1 2 1
2 3 2

Sample Input

input1
3 1
1 2 1
2 3 2
input 2
3 3
1 2 1
2 3 2

Sample Output

output1
1
2
output2
1
1
3/十的数量满意N <=三千0;
百分之百的数码满意贰 <=N<=
二.五*10^5、0<=xi,yi,li<=2*10^9,1<=L<=2*10^9,xi<=yi.

Sample Output

output1
1
2
output2
1
1
三成的多少满足N <=两千0;
百分百的数量满意二 <=N<=
二.5*10^5、0<=xi,yi,li<=2*10^9,1<=L<=2*10^9,xi<=yi.

HINT

 

HINT

 

Source

By
俞华程

 

题解

    发掘相差具有单调性质,所以能够想到单调性,将xi,xj抽象成一条线条,

    发掘当两条线段有混合的时候还要,距离满意条件时是足以转变的,

    那么如何考虑呢?

    发现能够将xi,xj离散化,这样的话,就足以在线段树1段距离中搜寻最小值,

    可是出现一个难题,最小值是不可见删除的,正是距离不满足了,怎么删除

    不能够形成,所以需求在种种点中开多个平淡队列,那才是那道难点的难点。

    

    先了然一个定义,什么叫做永世性flag,对于普通的flag,是否内需标志下传

    也正是说,标志不是牢固的,二恒久性标志,顾名思义便是不需求下传标志,

        图片 1

    比方革命线段是亟需探究的,那么对于包罗那条线段的,并且是满意整条线段包罗的

    作者的代码中分为多少个tr与1个bj数组,

    tr数组的情致是刚刚完全蕴涵那1段的,1个值,

    而bj表示子区间中含有这一段的,

    那么,在找出中,假诺被tr包蕴,tr可以间接更新,因为那段全体都是知足的。

    若是当前寻觅的那一段是归纳了bj那么bj中有子区间的值也迟早被寻觅段包罗,所以可以立异,

    那样立异前有限匡助单调性就可以。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<map>
 7 #include<list>
 8 
 9 #define N 2000007
10 #define inf 1000000007
11 #define fzy pair<int,int>
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n,L,num,siz;
22 int hd,tl,q[N],b[N],f[N];
23 struct Node
24 {
25     int x,y,l;
26 }a[N];
27 list<fzy>tr[N],bj[N];
28 map<int,int>p;
29 
30 
31 void ins(int p,int l,int r,int x,int y,fzy zhi)
32 {
33     if (x<=l&&r<=y)
34     {
35         while(!tr[p].empty()&&tr[p].back().second>=zhi.second)
36             tr[p].pop_back();
37         tr[p].push_back(zhi);
38         return;
39     }
40     
41     while(!bj[p].empty()&&bj[p].back().second>=zhi.second)
42         bj[p].pop_back();
43     bj[p].push_back(zhi);
44     
45     int mid=(l+r)>>1;
46     if (y<=mid) ins(p<<1,l,mid,x,y,zhi);
47     else if (x>mid) ins(p<<1|1,mid+1,r,x,y,zhi);
48     else ins(p<<1,l,mid,x,mid,zhi),ins(p<<1|1,mid+1,r,mid+1,y,zhi);
49 }
50 int query(int p,int l,int r,int x,int y,int wei)
51 {
52     int res;
53     
54     while(wei-tr[p].front().first>L&&!tr[p].empty())
55         tr[p].pop_front();
56     if (tr[p].empty()) res=inf;
57     else res=tr[p].front().second;
58     
59     
60     while(wei-bj[p].front().first>L&&!bj[p].empty()) bj[p].pop_front();
61     if (x<=l&&r<=y)
62     {
63         if (!bj[p].empty()) res=min(res,bj[p].front().second);
64         return res;
65     }
66     
67     int mid=(l+r)>>1;
68     if (y<=mid) res=min(res,query(p<<1,l,mid,x,y,wei));
69     else if (x>mid) res=min(res,query(p<<1|1,mid+1,r,x,y,wei));
70     else res=min(res,min(query(p<<1,l,mid,x,mid,wei),query(p<<1|1,mid+1,r,mid+1,y,wei)));
71     return res;
72 }
73 int main()
74 {
75     n=read(),L=read();
76     for (int i=1;i<n;i++)
77         a[i].x=read(),a[i].y=read(),a[i].l=read(),b[++num]=a[i].x,b[++num]=a[i].y;
78     sort(b+1,b+num+1);
79     for (int i=1;i<=num;i++)
80         if (b[i]!=b[i-1]) p[b[i]]=++siz;
81     for (int i=1;i<n;i++)
82         a[i].x=p[a[i].x],a[i].y=p[a[i].y];
83     
84     ins(1,1,siz,1,siz,make_pair(0,0));
85     for (int i=1;i<n;i++)
86     {
87         f[i]=query(1,1,siz,a[i].x,a[i].y,a[i].l)+1;
88         ins(1,1,siz,a[i].x,a[i].y,make_pair(a[i].l,f[i]));
89     }
90     for (int i=1;i<n;i++)
91         printf("%d\n",f[i]>=n?-1:f[i]);
92 }

 

Source

By
俞华程

 

题解

    开采距离具备单调性质,所以可以想到单调性,将xi,xj抽象成一条线条,

    开掘当两条线段有混合的时候还要,距离满意条件时是足以调换的,

    那么哪些思虑呢?

    开掘能够将xi,xj离散化,这样的话,就足以在线段树1段距离中追寻最小值,

    但是出现三个难点,最小值是无法删除的,正是距离不满意了,怎么删除

    不可能做到,所以须求在各类点中开二个单调队列,那才是那道难点的难点。

    

    先精晓一个概念,什么叫做永远性flag,对于一般的flag,是还是不是须求标志下传

    也便是说,标识不是定位的,二永远性标识,顾名思义即是不须求下传标识,

        图片 2

    例如革命线段是急需找出的,那么对于包蕴那条线段的,并且是满意整条线段包蕴的

    小编的代码中分成3个tr与2个bj数组,

    tr数组的情趣是刚刚完全包罗那一段的,一个值,

    而bj表示子区间中涵盖这1段的,

    那么,在探寻中,假使被tr包涵,tr能够向来更新,因为那段全体都是满意的。

    假诺当前寻觅的那壹段是归纳了bj那么bj中有子区间的值也自然被找寻段包涵,所以能够革新,

    那样创新前有限支撑单调性就可以。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<map>
 7 #include<list>
 8 
 9 #define N 2000007
10 #define inf 1000000007
11 #define fzy pair<int,int>
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n,L,num,siz;
22 int hd,tl,q[N],b[N],f[N];
23 struct Node
24 {
25     int x,y,l;
26 }a[N];
27 list<fzy>tr[N],bj[N];
28 map<int,int>p;
29 
30 
31 void ins(int p,int l,int r,int x,int y,fzy zhi)
32 {
33     if (x<=l&&r<=y)
34     {
35         while(!tr[p].empty()&&tr[p].back().second>=zhi.second)
36             tr[p].pop_back();
37         tr[p].push_back(zhi);
38         return;
39     }
40     
41     while(!bj[p].empty()&&bj[p].back().second>=zhi.second)
42         bj[p].pop_back();
43     bj[p].push_back(zhi);
44     
45     int mid=(l+r)>>1;
46     if (y<=mid) ins(p<<1,l,mid,x,y,zhi);
47     else if (x>mid) ins(p<<1|1,mid+1,r,x,y,zhi);
48     else ins(p<<1,l,mid,x,mid,zhi),ins(p<<1|1,mid+1,r,mid+1,y,zhi);
49 }
50 int query(int p,int l,int r,int x,int y,int wei)
51 {
52     int res;
53     
54     while(wei-tr[p].front().first>L&&!tr[p].empty())
55         tr[p].pop_front();
56     if (tr[p].empty()) res=inf;
57     else res=tr[p].front().second;
58     
59     
60     while(wei-bj[p].front().first>L&&!bj[p].empty()) bj[p].pop_front();
61     if (x<=l&&r<=y)
62     {
63         if (!bj[p].empty()) res=min(res,bj[p].front().second);
64         return res;
65     }
66     
67     int mid=(l+r)>>1;
68     if (y<=mid) res=min(res,query(p<<1,l,mid,x,y,wei));
69     else if (x>mid) res=min(res,query(p<<1|1,mid+1,r,x,y,wei));
70     else res=min(res,min(query(p<<1,l,mid,x,mid,wei),query(p<<1|1,mid+1,r,mid+1,y,wei)));
71     return res;
72 }
73 int main()
74 {
75     n=read(),L=read();
76     for (int i=1;i<n;i++)
77         a[i].x=read(),a[i].y=read(),a[i].l=read(),b[++num]=a[i].x,b[++num]=a[i].y;
78     sort(b+1,b+num+1);
79     for (int i=1;i<=num;i++)
80         if (b[i]!=b[i-1]) p[b[i]]=++siz;
81     for (int i=1;i<n;i++)
82         a[i].x=p[a[i].x],a[i].y=p[a[i].y];
83     
84     ins(1,1,siz,1,siz,make_pair(0,0));
85     for (int i=1;i<n;i++)
86     {
87         f[i]=query(1,1,siz,a[i].x,a[i].y,a[i].l)+1;
88         ins(1,1,siz,a[i].x,a[i].y,make_pair(a[i].l,f[i]));
89     }
90     for (int i=1;i<n;i++)
91         printf("%d\n",f[i]>=n?-1:f[i]);
92 }

 

相关文章