P2898 [USACO08JAN]haybale猜测Haybale Guessing

    • 107通过
    • 379提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 二分答案 并查集 线段树 USACO 2008 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    给一段长度为n,每个位置上的数都不同的序列a[1..n]和q和问答,每个问答是(x, y, r)代表RMQ(a, x, y) = r, 要你给出最早的有矛盾的那个问答的编号。

    输入输出格式

    输入格式:

    * 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
    
    输出样例#1: 复制
    3
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。