Lucky prefixes

input/code.cpp: In function 'll best_prefix(int, int)':
input/code.cpp:42: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]
   42 |   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];
 
const ll LINF = (1LL<<56LL);

pair<ll, ll> combine(pair<ll, ll> left, pair<ll, ll> right) {
  ll totsum = left.first + right.first;
  if (totsum < -LINF) totsum = -LINF;
  ll max_prefix = max((ll)left.second, (ll)((ll)left.first + (ll)right.second));
  if (max_prefix < -LINF) max_prefix = -LINF;
  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 upd(int pos, ll x) {
  pos += N;
  vals[pos] = x;
  // cout << "vals["<<pos<<"] = "<<x<<"\n";
  seg[pos] = make_pair(x, x);
  // cout << "seg pos done too\n";
  for (pos /= 2; pos >= 1; pos /= 2) {
    seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
  }
}
 
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
 
  int n, m;
  cin>>n>>m;
 
  // cout << "I have "<<n<<" "<<m<<"\n";
 
  for (int i = 0; i < n; i++) {
    ll x; cin>>x;
    vals[i] = -x;
  }
 
  // cout << "printing arr:\n";
  for (int i = 0; i < n; i++) {
    // cout << vals[i]<<" ";
  }
 
  build_segtree(n);
 
  for (int qi = 0; qi < m; qi++) {
    // cout << "hi? here m is "<<m<<" and qi is "<<qi<<"\n";
    int qt = 0;
    cin>>qt;
    if (qt == 2) {
      int a = 0;
      int b = 0;
      cin>>a>>b;
      a = max(a, 1);
      b = min(b, n);
      // query
      ll res = -best_prefix(a-1, b-1);
      // cout << "minimum of "<<x-1<<" "<<y-1<<" interval is "<<res<<"\n";
      if (res < 0LL) cout << "NO\n";
      else cout << "YES\n";
    } else {
      int pos = 0;
      ll v = 0;
      cin>>pos>>v;
      // cout << "setting "<<x-1<<" to value"<<-y<<" and a was "<<a<<"\n";
      upd(pos-1, -v);
      // cout << "set it?\n";
    }
    // cout << "will continue because "<<qi<<" "<<m<<"\n";
  }
}

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