Operacije niza

Neka je dat niz celih brojeva \(\mathbf{a}\) veličine \(n\). Dalje, neka je dato \(m\) operacija oblika \(l\ r\ d\), koje uvećavaju elemenate, koji se nalaze na pozicijama između \(l\) i \(r\), niza \(\mathbf{a}\) za vrednost \(d\). Drugim rečima, ukoliko primenimo uopraciju \(l\ r\ d\), onda niz \(\mathbf{a}\) postaje oblika \(\mathbf{a}_0, \mathbf{a}_1, \ldots, \mathbf{a}_{l - 1}, \mathbf{a}_l + d, \ldots, \mathbf{a}_r + d, \mathbf{a}_{r + 1}, \ldots, \mathbf{a}_r\). Na kraju, neka je dato \(k\) upita oblika \(x\), gde svaki upit predstavlja primenu operacije \(l_x\ r_x\ d_x\).

Odrediti konačno stanje niza.

Opis ulaza

Sa standardnog ulaza se, redom, unose vrednost \(n, m, k\) (\(1 \leq n, m, k \leq 10^5\)). U sledećoj liniji, se unosi \(n\) elemenata niza \(\mathbf{a}\) (\(1 \leq \mathbf{a}_i \leq 100\)). U sledećih \(m\) linija, se unose operacije oblike \(l_j\ r_j\ d_j\) (\(0 \leq l_j \leq r_j < n, 0 < d < 10, 0 < j \leq m\)), svaka u zasebnoj liniji. U sledećih \(k\) linija, se unose upiti oblika \(x_i\) (\(0 \leq x_i < m\)), svaki u zasebnoj liniji.

Opis izlaza

Na standardni izlaz ispisati izmenjeno stanje niza \(\mathbf{a}\).

Primer 1

Ulaz

3 3 5
1 2 3
0 1 1
0 2 2
1 2 4
0 
1
0 
2
1

Izlaz

7 12 11

Primer 2

Ulaz

1 1 1
1
0 0 1
0

Izlaz

2

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main() 
{
    int n, m, k; cin >> n >> m >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<tuple<int, int, int>> op(m);
    for (int i = 0; i < m; i++) {
        int l, r, d; cin >> l >> r >> d;

        op[i] = { l, r, d };
    }

    vector<int> count(m);
    for (int i = 0; i < k; i++) {
        int x; cin >> x;

        count[x]++;
    }
    
    vector<int> to_add(n + 1, 0);
    for (int i = 0; i < m; i++) {
        const auto &[l, r, d] = op[i];

        to_add[l] += count[i] * d;
        to_add[r + 1] -= count[i] * d;
    }

    for (int i = 1; i <= n; i++) {
        to_add[i] += to_add[i - 1];
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i] + to_add[i] << " ";
    }
    cout << endl;
    

    return 0;
}
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

int main()
{
    int n, m, k; cin >> n >> m >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<tuple<int, int, int>> op(m);
    for (int i = 0; i < m; i++) {
        int l, r, d; cin >> l >> r >> d;
        op[i] = { l, r, d };
    }

    while(k--) {
        int x; cin >> x;

        const auto &[l, r, d] = op[x];
        for (int i = l; i <= r; i++) {
            arr[i] += d;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}