NC24951. [USACO 2008 Jan G]Haybale Guessing
描述
输入描述
* Line 1: Two space-separated integers: N and Q
* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A
输出描述
* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.
示例1
输入:
20 4 1 10 7 5 19 7 3 12 8 11 15 12
输出:
3
说明:
The minimum number of bales in stacks 1..10 is 7, the minimum number of bales in stacks 5..19 is 7, the minimum number of bales in stacks 3..12 is 8, and the minimum number of bales in stacks 11..15 is 12.C++14(g++5.4) 解法, 执行用时: 81ms, 内存消耗: 5340K, 提交时间: 2019-07-28 17:18:02
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define M 30000
#define inf 0x3f3f3f3f
using namespace std;
struct Lux
{
int l,r,x;
bool operator < (const Lux &a)const{return x>a.x;}
}q[M],Q[M];
int n,m,f[N];
int stk[N],top;
int find(int x)
{
top=0;
while(f[x]!=x)stk[++top]=x,x=f[x];
while(top)f[stk[top--]]=x;
return x;
}
bool check(int mid)
{
int i,j,k,t;
int L,R,l,r;
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=mid;i++)q[i]=Q[i];
sort(q+1,q+mid+1);
for(i=1;i<=mid;i=j+1)
{
L=l=q[i].l,R=r=q[i].r;
for(j=i;j<mid&&q[j+1].x==q[j].x;)
{
j++;
L=min(L,q[j].l),R=max(R,q[j].r);
l=max(l,q[j].l),r=min(r,q[j].r);
}
if(find(r)<l)return 0;
for(t=R;k=find(t),k>=L;t=k-1)f[k]=L-1;
}
return 1;
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
int l,r,mid,ans;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].x);
l=1,r=m,ans=0;
for(i=1;i<=20&&l<=r;i++)
{
mid=l+r>>1;
if(check(mid))l=mid+1;
else ans=mid,r=mid-1;
}
printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 4956K, 提交时间: 2020-02-15 16:33:50
#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
#define N 1001000
#define M 30000
using namespace std;
struct haha
{
int l,r,x;
bool operator < (const haha &a)const
{
return x>a.x;
}
}q[M],Q[M];
int n,m,f[N];
int stk[N],top;
int find(int x)
{
top=0;
while(f[x]!=x)
stk[++top]=x,x=f[x];
while(top)
f[stk[top--]]=x;
return x;
}
bool check(int mid)
{
int i,j,k,t;
int L,R,l,r;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=mid;i++)
q[i]=Q[i];
sort(q+1,q+mid+1);
for(i=1;i<=mid;i=j+1)
{
L=l=q[i].l,R=r=q[i].r;
for(j=i;j<mid&&q[j+1].x==q[j].x;)
{
j++;
L=min(L,q[j].l),R=max(R,q[j].r);
l=max(l,q[j].l),r=min(r,q[j].r);
}
if(find(r)<l)
return 0;
for(t=R;k=find(t),k>=L;t=k-1)
f[k]=L-1;
}
return 1;
}
int main()
{
int i,j,k;
int l,r,mid,ans;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].x);
l=1,r=m,ans=0;
for(i=1;i<=20&&l<=r;i++)
{
mid=l+r>>1;
if(check(mid))
l=mid+1;
else
ans=mid,r=mid-1;
}
printf("%d\n",ans);
return 0;
}