The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.A designated 'Hay Cow' hides behind the barn and creates N (1 ?? N ?? 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.The other cows then ask the Hay Cow a series of Q (1 ?? Q ?? 25,000) questions about the the stacks, all having the same form:What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ?? Ql ?? N; Ql ?? Qh ?? N)?The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.
???鼯+?????
?????????ì????????
????е??????????????κ??????????????????????????С????????????н????????????????????ì???
??????????????????С?????С???????????ì???
?????????ж?????????С?
???????ì??????????????????????С???С????????鼯?????????????????????????????????????鼯???????????????????????????????????鼯????????????????????????????????????????????????????????????????????????δ????????????????????????????????????ì??? 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using namespace std;
typedef long long ll;
inline void getint(int &x)
{
char c;
for(c=getchar();c>'9'||c<'0';c=getchar());
for(x=0;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
}
const int MAXN=1000000+5;
struct Seg
{
int l,r,v;
}e[MAXN];
int lim,n;
int srt[MAXN],fa[MAXN];
bool cmp(int a,int b)
{
if(e[a].v==e[b].v)
return e[a].l==e[b].l?e[a].r<e[b].r:e[a].l<e[b].l;
return e[a].v>e[b].v;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool check(int mid)
{
for(rint i=1;i<=mid;++i)
srt[i]=i;
for(rint i=1;i<=lim;++i)
fa[i]=i;
sort(srt+1,srt+mid+1,cmp);
int x,y;
for(int i=1;i<=mid;++i)
{
int t=e[srt[i]].v,l=e[srt[i]].l,
r=e[srt[i]].r,lm=e[srt[i]].l,rm=e[srt[i]].r;
while(i+1<=mid&&t==e[srt[i+1]].v)
{
++i;
if(e[srt[i]].l>r)
return 0;
l=max(l,e[srt[i]].l);
r=min(r,e[srt[i]].r);
lm=min(lm,e[srt[i]].l);
rm=max(rm,e[srt[i]].r);
}
int x=find(l),y=find(r);
if((l!=r&&x==y&&y!=r)||(l==r&&y!=r)) //??????ж?
return 0;
x=lm,y=rm;
int rg=find(y+1);
while(rg!=find(x))
{
int fx=find(x);
fa[fx]=fa[fx+1];
}
}
return 1;
}
int main()
{
scanf("%d%d",&lim,&n);
for(int i=1;i<=n;++i)
getint(e[i].l),getint(e[i].r),getint(e[i].v);
int l=1,r=n+1;
while(r-l>1)
{
int mid=l+r>>1;
if(check(mid))
l=mid;
else r=mid;
}
printf("%d",l==n?0:l+1);
return 0;
}