Lucky prefixes

input/code.cpp: In function 'll best_prefix(int, int)':
input/code.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 1; i < all_chunks.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (1 << 18);
pair<ll, ll> seg[2*N];
ll vals[N];
ll csum[N];

const ll LINF = (1LL<<58LL);

pair<ll, ll> combine(pair<ll, ll>& left, pair<ll, ll>& right) {
  ll totsum = left.first + right.first;
  ll max_prefix = max(left.second, left.first + right.second);
  return make_pair(totsum, max_prefix);
}

ll best_prefix(int a, int b) {
  a += N;
  b += N;

  vector<pair<ll, ll>> left_chunks;
  vector<pair<ll, ll>> right_chunks;
  while (a <= b) {
    if (a % 2 == 1) left_chunks.push_back(seg[a++]);
    if (b % 2 == 0) right_chunks.push_back(seg[b--]);
    a /= 2;
    b /= 2;
  }

  reverse(right_chunks.begin(), right_chunks.end());

  vector<pair<ll, ll>> all_chunks;

  for (auto v : left_chunks) all_chunks.push_back(v);
  for (auto v : right_chunks) all_chunks.push_back(v);

  pair<ll, ll> result = all_chunks[0];
  for (int i = 1; i < all_chunks.size(); i++) {
    result = combine(result, all_chunks[i]);
  }

  return result.second;
}

void build_segtree(int n) {
  for (int i = 0; i < n; i++) {
    seg[i + N] = make_pair(vals[i], vals[i]);
  }
  for (int i = N + n; i < 2*N; i++) {
    seg[i] = make_pair(-LINF, -LINF);
  }

  for (int i = N - 1; i >= 1; i--) {
    seg[i] = combine(seg[2*i], seg[2*i+1]);
  }
}

void update(int pos, ll x) {
  pos += N;
  vals[pos] = x;
  seg[pos] = {x, x};
  for (pos /= 2; pos >= 1; pos /= 2) {
    seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
  }
}

int n, m;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>m;

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

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

  build_segtree(n);

  for (int qi = 0; qi < m; qi++) {
    int qt;
    cin>>qt;
    if (qt == 2) {
      // query
      int a, b;
      cin>>a>>b;
      a--;
      b--;
      ll res = -best_prefix(a, b);
      if (res < 0) cout << "NO\n";
      else cout << "YES\n";
    } else {
      int i;
      ll x;
      cin>>i>>x;
      x = -x;
      i--;
      update(i, x);
    }
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER