Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
A. Грег ба массив
хугацааны хязгаарлалт 1.5 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Грэгд $a= a_1 , a_2 , a_3… a_n$ массив болон $m$ үйлдэл байв.Үйлдэл болгон $l_i , r_i , d_i$ ($1≤l_i ≤r_i≤n$) –г ажигдладаг ба $i$-р үйлдэлийг хийнэ гэдэг нь $l_i, l_i +1,... r_i$ элементтэй массивын бүх гишүүдийг $d_i$ аар нэмэгдүүлнэ гэсэн үг. Грэг цаасан дээр K ширхэг асуултын тэмдэг бичnв.Асуултын тэмдэг болгон дараах хэлбэртэй : $x_i, y_i$, ($1 ≤ x_i ≤ y_i ≤ m$).Энэ нь аль 1 асуултын тэмдгийг массивруу $x_i, x_i + 1, ..., y_i$ элемэнттэй үйлдлээр оруулна гэсэн үг. Бүх асуултын тэмдэг дуусахад а массивд ямар өөрчлөлт орох вэ ?
Оролт
Эхний мөрөнд бүхэл $n , m , k$ ($1 ≤ n, m, k ≤ 10^5$)-г агуулна. 2-р мөрөнд бүхэл n $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^5$)-г агуулна – эхний массив Дараагийн m мөр нь үйлдлүүдийг агуулах ба $i$-дугаар мөр нь 3 бүхэл тоо $l_i, r_i, d_i$, ($1 ≤ l_i ≤ r_i ≤ n$), ($0 ≤ d_i ≤ 10^5$) хэлбэрээр бичигдэнэ. Дараагийн k мөр нь асуултын тэмдгүүдийг агуулах ба $i$-дах асуултын тэмдэг нь 2 бүхэл тоо $x_i$, $y_i$, ($1 ≤ x_i ≤ y_i ≤ m$) хэлбэрээр бичигдэнэ. Мөрнүүдэд байгаа тоонууд зайгаар тусгаарлагдсан байна.
Гаралт
Бүх асуултын тэмдэг дууссаны дараа энгийн мөрөнд $n$ ширхэг бүхэл тоог хэвлэнэ $a_1, a_2, ..., a_n$ . Хэвлэсэн тоонууд хоорондоо зайтай байна.
[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]
Орчуулсан: Баттулга
Жишээ тэстүүд
Оролт
3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3
Гаралт
9 18 17
Оролт
1 1 1 1 1 1 1 1 1
Гаралт
2
Оролт
4 3 6 1 2 3 4 1 2 1 2 3 2 3 4 4 1 2 1 3 2 3 1 2 1 3 2 3
Гаралт
5 18 31 20