The Cosmic Era P3 - Battle Positions - Olympiads Online Judge

The Cosmic Era P3 - Battle Positions

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 0.1s

Java 0.6s

Python 0.6s

Memory limit: 128M

Author:

LOLWHATOMGBBQ

Problem type

The ZAFT are attacking the Orb Union! There are $I$ $I$ stations, numbered from $1, 2, \dots, I$ $1, 2, \dots, I$ , that need to be defended. For it to be secure, the Orb Union needs to have at least $N$ $N$ troops at each station. Unfortunately, due to the radar-jamming effects of the Neutron Jammer, the Orb Union cannot order their troops to move between stations. The Orb Union will send $J$ $J$ waves of troops, each of which sends $K$ $K$ troops to each of the stations $X_i, X_{i+1}, \dots, X_f$ $X_{i}, X_{i + 1}, \dots, X_{f}$ . All stations start with $0$ $0$ troops.

The Orb Union wants you to help them find the number of stations that are not secure.

Input Specification

The first line will contain the integer $I$ $I$ $(1 \le I \le 10^5)$ $(1 \leq I \leq 10^{5})$ , the number of stations.

The second line will contain the integer $N$ $N$ $(1 \le N \le 10^9)$ $(1 \leq N \leq 10^{9})$ , the minimum number of troops required to defend a station.

The third line will contain the integer $J$ $J$ $(1 \le J \le 10^5)$ $(1 \leq J \leq 10^{5})$ , the number of waves of troops.

The next $J$ $J$ lines will contain 3 space-separated integers. These integers will be in the order $X_i$ $X_{i}$ , $X_f$ $X_{f}$ , $K$ $K$ $(1 \le X_i \le X_f \le I)$ $(1 \leq X_{i} \leq X_{f} \leq I)$ $(1 \le K \le 10^4)$ $(1 \leq K \leq 10^{4})$ .

Output Specification

Output the total number of stations that have less than $N$ $N$ troops.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

Station 1 has 1 troop, station 2 has 3 troops, station 3 has 5 troops and station 4 has 0 troops. Station 4 is the only station with less than 1 troop, so the output is 1.

Comments

0

sre0x2a commented on Feb. 3, 2024, 2:26 p.m.

Is there a better than linear time way to sum the values in a sub-array of an array?

-1

catamaran_detergent commented on July 11, 2024, 1:22 a.m.

the problem type is data structures, not implementation. there's probably a better way to solve it. also, look at the time restrictions lol

-90

Plasmatic commented on March 18, 2017, 2:56 p.m.

lol this is anime :P

This comment is hidden due to too much negative feedback. Show it anyway.