#1310. USACO 2020 February Contest, Gold — Problem 1. Timeline

    ID: 1310 传统题 文件IO:timeline 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases线段树差分

USACO 2020 February Contest, Gold — Problem 1. Timeline

USACO 2020 February Contest, Gold — Problem 1. Timeline

题目描述

Bessie attended NN milking sessions (1≤N≤1051\le N\le 10^5) over the past MM days (2≤M≤1092 \le M \le 10^9). However, she is having trouble remembering when she attended each session. For each session i=1…Ni = 1 \ldots N, she knows that it occurred no earlier than day SiS_i (1≤Si≤M1\le S_i\le M). Additionally, Bessie has CC memories (1≤C≤1051\le C\le 10^5), each described by a triple (a,b,x)(a,b,x), where she recalls that session bb happened at least xx days after aa. Help Bessie by computing the earliest possible date of occurrence for each milking session. It is guaranteed that Bessie did not remember incorrectly; in other words, there exists an assignment of sessions to days in the range 1…M1\ldots M such that all constraints from her memories are satisfied.

输入格式

The first line of input contains NN, MM, and CC. The next line contains NN space-separated integers S1,S2,…,SNS_1,S_2,\ldots, S_N. Each is in the range 1…M1 \ldots M. The next CC lines contain three integers, aa, bb, and xx indicating that session bb happened at least xx days after aa. For each line, a≠ba \neq b, aa and bb are in the range 1…N1 \ldots N, and xx is in the range 1…M1 \ldots M.

输出格式

(见题面原文)

数据范围

Test cases 2-4 satisfy N,C≤103N,C \le 10^3. Test cases 5-10 satisfy no additional constraints.

样例

样例 1

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
1
6
3
8
Session two occurred at least five days after session one, so it cannot have
occurred before day $1+5=6.$ Session four occurred at least two days after session
two, so it cannot have occurred before day $6+2=8$.
Problem credits: Mark Gordon