Submission #70835729

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template <typename T>
using vc = vector<T>;

void solve() {
  int N, Q;
  cin >> N >> Q;

  vc<ll> C(N - 1);  // A[i]+C[i]<A[i+1]
  vc<ll> ADD(N);

  for (int q = 0; q < Q; ++q) {
    int i, x;
    cin >> i >> x;
    --i;
    ADD[i] += x;
    if (i < N - 1) {
      // A[i] + ADD[i] < A[i+1] + ADD[i+1]
      C[i] = max(C[i], ADD[i] - ADD[i + 1]);
    }
  }

  vc<ll> A(N);
  A[0] = 1;
  for (int i = 0; i < N - 1; ++i) A[i + 1] = A[i] + C[i] + 1;

  ll ANS = 0;
  for (int i = 0; i < N; ++i) ANS += A[i];

  cout << ANS << "\n";
}

signed main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  solve();
}

Submission Info

Judge Result