Lucky prefixes

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

#include <bits/stdc++.h>

using namespace std;

typedef long long myll;
typedef __int128 ll;

const int N = (1 << 18);
pair<ll, ll> seg[2*N];
ll vals[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((ll)left.second, (ll)(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);

//   cout<<"all chunks: \n";
//   for (int i = 0; i < all_chunks.size(); i++) {
//     cout << "chunk "<<i<<" has: "<<all_chunks[i].first<<" "<<all_chunks[i].second<<"\n";
//   }

  pair<ll, ll> result = all_chunks[0];
  for (int i = 1; i < all_chunks.size(); i++) {
    // cout << "at ("<<a<<", "<<b<<") we have chunks: "<<result.first<<" "<<result.second<<"  AND  "<<all_chunks[i].first<<" "<<all_chunks[i].second<<"\n";
    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) {
    // cout << "seg["<<pos<<"] ans before: "<<seg[pos].first<<" "<<seg[pos].second<<"\n";
    seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
    // cout << "after: "<<seg[pos].first<<" "<<seg[pos].second<<"\n";
  }
}


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++) {
    myll x; cin>>x;
    vals[i] = -x;
  }

  // cout << "printing arr:\n";
  // for (int i = 0; i < n; i++) {
  //   upd(i, vals[i]);
  // }

  build_segtree(n);

  for (int qi = 0; qi < m; qi++) {
    // cout << "hi? here m is "<<m<<" and qi is "<<qi<<"\n";
    myll a, x, y;
    cin>>a>>x>>y;
    if (a == 2) {
      // query
      ll res = -best_prefix(x-1, y-1);
      // cout << "minimum of "<<x-1<<" "<<y-1<<" interval is "<<res<<"\n";
      if (res < 0LL) cout << "NO\n";
      else cout << "YES\n";
    } else {
      // cout << "setting "<<x-1<<" to value"<<-y<<" and a was "<<a<<"\n";
      upd(x-1, -y);
      // 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