-
-
Save Earne/e3688d93a74ae2f8b068 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Rainfall | |
| Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) | |
| Problem Description: | |
| 葫芦大道（The Hulu Way）上有N间房子，分别位于坐标Ai 。这里常年多雨，一年能有近10w天在下雨（可怕。。。）。葫芦大道上还住着一位武男，他统计了这一年下雨的情况，每次下雨他会记下三个数据，Li，Ri和Wi，表示今天所有坐标在Li和Ri之间（包括Li和Ri）的所有房子，都淋了Wi这么长时间的雨。现在武男想知道，这一年里，每间房子总共都淋了多长时间的雨。 | |
| 输入 | |
| 输入的第一行是一个整数N(1 <= N <= 10^5)。 | |
| 接下来一行N个整数Ai(0 <= Ai < 2^31)，房子的坐标按递增序给出。 | |
| 接下来一行是整数M(1 <= M <= 10^5)。 | |
| 然后M行，每行三个整数分别为Li，Ri(0 <= Li <= Ri < 2^31)和Wi(1 <= Wi <= 10^4)。 | |
| 输出 | |
| N行每行一个数字，依次为每间房子全年总共的淋雨时长。 | |
| 样例输入 | |
| 5 | |
| 1 3 5 7 9 | |
| 2 | |
| 2 8 5 | |
| 1 5 4 | |
| 样例输出 | |
| 4 | |
| 9 | |
| 9 | |
| 5 | |
| 0 | |
| import java.util.*; | |
| /** | |
| * Created by Earne on 2015/9/26. | |
| 5 | |
| 1 3 5 7 9 | |
| 2 | |
| 2 8 5 | |
| 1 5 4 | |
| */ | |
| public class Main { | |
| public static void main(String[] args) { | |
| Scanner cin = new Scanner(System.in); | |
| int N = cin.nextInt(); | |
| TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); | |
| while (N-- != 0) { | |
| map.put(cin.nextInt() - 1, 0); | |
| } | |
| int M = cin.nextInt(); | |
| while (M-- != 0) { | |
| int L = cin.nextInt(); | |
| int R = cin.nextInt(); | |
| int W = cin.nextInt(); | |
| Map<Integer, Integer> sorted = map.subMap(L - 1, R); | |
| for (Map.Entry<Integer, Integer> entry : sorted.entrySet()) { | |
| entry.setValue(entry.getValue() + W); | |
| } | |
| } | |
| for (Integer iter : map.values()) { | |
| System.out.println(iter); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment