Submission details
Task:Lucky prefixes
Sender:Works on my Machine
Submission time:2025-11-08 14:08:11 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.25 sdetails
#30.00 sdetails
#40.14 sdetails
#50.34 sdetails
#60.18 sdetails
#70.20 sdetails
#80.26 sdetails
#90.33 sdetails
#100.00 sdetails
#110.14 sdetails
#120.33 sdetails
#130.18 sdetails
#140.20 sdetails
#150.27 sdetails
#160.33 sdetails

Compiler report

input/code.cpp: In constructor 'SegmentTree::SegmentTree(int)':
input/code.cpp:13:7: warning: 'SegmentTree::n' will be initialized after [-Wreorder]
   13 |   int n;
      |       ^
input/code.cpp:12:26: warning:   'std::vector<long long int> SegmentTree::s' [-Wreorder]
   12 |   std::vector<long long> s;
      |                          ^
input/code.cpp:15:3: warning:   when initialized here [-Wreorder]
   15 |   SegmentTree(int n):n(n),s(2*n, unit){}
      |   ^~~~~~~~~~~

Code

#include "vector"

struct SegmentTree {
  long long unit = 0;
  long long op(long long a, long long b){
    if (a >= 0) {
      return a+b;
    } else {
      return a;
    }
  }
  std::vector<long long> s; 
  int n;
  
  SegmentTree(int n):n(n),s(2*n, unit){}
  void update(int pos, long long val){
    for (s[pos+=n] = val; pos/=2;)
      s[pos] = op(s[pos*2], s[pos*2 + 1]);
  }
  long long query(int lo, int hi){
    long long ra = unit;
    long long rb = unit;
    for (lo+=n, hi+=n; lo<hi; lo/=2, hi/=2){
      if (lo % 2) ra = op(ra, s[lo++]);
      if (hi % 2) rb = op(s[--hi], rb);
    }
    return op(ra, rb);
  }
};


#include <iostream>
int main(){
  int n, q;
  std::cin >> n >> q;
  SegmentTree tree(n);
  // std::vector<long long> prefixSum(n);
  for (int i = 0; i<n; ++i){
    long long num;
    std::cin >> num;
    tree.update(i, num);
  }

  
  std::vector<bool> query;

  for (int i = 0; i<q; ++i){
    int q;
    int a;
    int b;
    std::cin >> q >> a >> b;
    if (q==1){
      tree.update(a-1, b);
    }else {
      if (tree.query(a-1, b-1) >= 0) {
        query.push_back(true);
      } else {
        query.push_back(false);
      }
    }
  }

  for (bool q: query){
    if (q){
      std::cout << "YES\n";
    } else {
      std::cout << "NO\n";
    }
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
6 4
3 -2 1 5 6 1
2 1 3
2 2 3
1 3 -2
...

correct output
YES
NO
NO

user output
YES
NO
NO

Test 2

Verdict:

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
NO
NO
NO
NO
NO
...

user output
NO
YES
NO
YES
NO
...

Feedback: Incorrect character on line 2 col 1: expected "NO", got "YES"

Test 3

Verdict:

input
10 10
629447384 -729045992 811583872...

correct output
YES
NO
NO
NO
NO
...

user output
YES
YES
NO
YES
NO
...

Feedback: Incorrect character on line 2 col 1: expected "NO", got "YES"

Test 4

Verdict:

input
1 200000
629447384
1 1 670017180
1 1 826751744
1 1 -804919168
...

correct output
NO
NO
NO
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Feedback: Incorrect character on line 1 col 1: expected "NO", got "YES"

Test 5

Verdict:

input
200000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 16 col 1: expected "NO", got "YES"

Test 6

Verdict:

input
1000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 7 col 1: expected "NO", got "YES"

Test 7

Verdict:

input
10000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
YES
...

Feedback: Incorrect character on line 5 col 1: expected "NO", got "YES"

Test 8

Verdict:

input
100000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
YES
NO
NO
...

Feedback: Incorrect character on line 3 col 1: expected "NO", got "YES"

Test 9

Verdict:

input
200000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 16 col 1: expected "NO", got "YES"

Test 10

Verdict:

input
10 10
629447384 -729045992 811583872...

correct output
YES
NO
NO
NO
NO
...

user output
YES
YES
NO
YES
NO
...

Feedback: Incorrect character on line 2 col 1: expected "NO", got "YES"

Test 11

Verdict:

input
1 200000
629447384
1 1 670017180
1 1 826751744
1 1 -804919168
...

correct output
NO
NO
NO
YES
YES
...

user output
YES
YES
YES
YES
YES
...

Feedback: Incorrect character on line 1 col 1: expected "NO", got "YES"

Test 12

Verdict:

input
200000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 16 col 1: expected "NO", got "YES"

Test 13

Verdict:

input
1000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 7 col 1: expected "NO", got "YES"

Test 14

Verdict:

input
10000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
YES
...

Feedback: Incorrect character on line 5 col 1: expected "NO", got "YES"

Test 15

Verdict:

input
100000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
YES
NO
NO
...

Feedback: Incorrect character on line 3 col 1: expected "NO", got "YES"

Test 16

Verdict:

input
200000 200000
629447384 -729045992 811583872...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...

Feedback: Incorrect character on line 16 col 1: expected "NO", got "YES"