Language: C++

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10, inf = 1e9;

int n, m;
int arr[maxn];
int sum[maxn];
int dp[maxn];

vector<int> begins[maxn];
vector<int> ended[maxn];

int mxm[4 * maxn];
int mnm[4 * maxn];

vector<int> to_update[maxn];

int update_mxm(int i, int l, int r, int x, int v) {
    if(l == r) {
        if(l == x)
            mxm[i] = v;
        return mxm[i];
    }

    if(l > x || r < x)
        return mxm[i];

    int m = (l + r + 1) / 2;

    return mxm[i] = max(update_mxm(i * 2, l, m - 1, x, v), update_mxm(i * 2 + 1, m, r, x, v));
}

int query_mxm(int i, int l, int r, int ql, int qr) {
    if(l >= ql && r <= qr)
        return mxm[i];

    if(l > qr || r < ql)
        return 0;

    int m = (l + r + 1) / 2;

    return max(query_mxm(i * 2, l, m - 1, ql, qr), query_mxm(i * 2 + 1, m, r, ql, qr));
}

int update_mnm(int i, int l, int r, int x, int v) {
    if(l == r) {
        if(l == x)
            mnm[i] = v;
        return mnm[i];
    }

    if(l > x || r < x)
        return mnm[i];

    int m = (l + r + 1) / 2;

    return mnm[i] = min(update_mnm(i * 2, l, m - 1, x, v), update_mnm(i * 2 + 1, m, r, x, v));
}

int query_mnm(int i, int l, int r, int ql, int qr) {
    if(l >= ql && r <= qr)
        return mnm[i];

    if(l > qr || r < ql)
        return inf;

    int m = (l + r + 1) / 2;

    return min(query_mnm(i * 2, l, m - 1, ql, qr), query_mnm(i * 2 + 1, m, r, ql, qr));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }

    cin >> m;

    for(int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        begins[a].push_back(b);
        ended[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        sort(begins[i].begin(), begins[i].end());
        sort(ended[i].begin(), ended[i].end());
    }

    for(int i = 1; i <= n; i++)
        update_mnm(1, 1, n, i, inf);

    for(int i = n; i >= 1; i--) {
//        cout << i << endl;

        for(int j : to_update[i]) {
            update_mnm(1, 1, n, j, j - sum[j] + dp[j + 1]);
        }

        int mn = i;
        int mx = i;

        if(!begins[i].empty()) {
            mn = begins[i].front();
            mx = max(mx, query_mxm(1, 1, n, i, begins[i].back()));
        }

        dp[i] = arr[i] + dp[i + 1];

//        cout << "query_mnm je " << query_mnm(1, 1, n, mn, mx) << endl;

        dp[i] = min(dp[i], query_mnm(1, 1, n, mn, mx) - i + 1 + sum[i - 1]);

        if(!ended[i - 1].empty()) {
            to_update[ended[i - 1].back()].push_back(i - 1);
        }

        update_mxm(1, 1, n, i, mx);

//        cout << i << ", dp je " << dp[i] << " mn: " << mn << " mx: " << mx << endl;
//
//        for(int i = 1; i <= n; i++)
//            cout << query_mnm(1, 1, n, i, i) << " ";
//        cout << endl;

//        for(int i = 1; i <= n; i++)
//            cout << query_mxm(1, 1, n, i, i) << " ";
//        cout << endl;
//        cout << endl;
    }

    cout << dp[1] << endl;

    return 0;
}


Compiler output:
a.cc:13:1: error: 'vector' does not name a type
   13 | vector<int> begins[maxn];
      | ^~~~~~
a.cc:14:1: error: 'vector' does not name a type
   14 | vector<int> ended[maxn];
      | ^~~~~~
a.cc:19:1: error: 'vector' does not name a type
   19 | vector<int> to_update[maxn];
      | ^~~~~~
a.cc: In function 'int main()':
a.cc:90:9: error: 'begins' was not declared in this scope
   90 |         begins[a].push_back(b);
      |         ^~~~~~
a.cc:91:9: error: 'ended' was not declared in this scope
   91 |         ended[b].push_back(a);
      |         ^~~~~
a.cc:95:14: error: 'begins' was not declared in this scope
   95 |         sort(begins[i].begin(), begins[i].end());
      |              ^~~~~~
a.cc:96:14: error: 'ended' was not declared in this scope
   96 |         sort(ended[i].begin(), ended[i].end());
      |              ^~~~~
a.cc:105:21: error: 'to_update' was not declared in this scope
  105 |         for(int j : to_update[i]) {
      |                     ^~~~~~~~~
a.cc:112:13: error: 'begins' was not declared in this scope
  112 |         if(!begins[i].empty()) {
      |             ^~~~~~
a.cc:123:13: error: 'ended' was not declared in this scope
  123 |         if(!ended[i - 1].empty()) {
      |             ^~~~~
a.cc:124:13: error: 'to_update' was not declared in this scope
  124 |             to_update[ended[i - 1].back()].push_back(i - 1);
      |             ^~~~~~~~~