Problem p02599 (python)

Fixed submission:

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
class Query:
    def __init__(self, i, l, r):
        self.i = i
        self.l = l
        self.r = r
    
    
N, Q = map(int, input().split())
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
from dataclasses import dataclass
    
class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
@dataclass
class Query:
    i: int
    l: int
    r: int
    
    
N, Q = map(int, input().split())
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
V = max(C)
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
    from dataclasses import dataclass
     
    class BIT:
        '''
        All methods use 0-based index while the implementation use 1-based index
        '''
        def __init__(self, N, val=0):
            self.data = [val] * (N + 1)
            self.N = N
     
        def add_at(self, idx, val):
            i = idx + 1
            while i <= self.N:
                self.data[i] += val
                i += i & (-i)
     
        def sum_to(self, idx):
            res = 0
            i = idx + 1
            while i > 0:
                res += self.data[i]
                i -= i & (-i)
            return res
     
        def sum_in(self, l, r): # [l, r]
            return self.sum_to(r) - self.sum_to(l - 1)
     
     
    @dataclass
    class Query:
        i: int
        l: int
        r: int
     
     
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
     
    queries = [[] for _ in range(N)]
    for i in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        queries[r].append(Query(i, l, r))
     
    V = max(C)
    bit = BIT(N)
    last = [-1] * (V + 1)
     
    query_idx = 0
    ans = [-1] * Q
    for i, c in enumerate(C):
        if last[c] != -1:
            bit.add_at(last[c], -1)    
        bit.add_at(i, +1)
        last[c] = i
     
        for q in queries[i]:
            ans[q.i] = bit.sum_in(q.l, q.r)
     
    print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

template<class T>
struct BIT {
    int N;
    vector<T> data;
    BIT(int N) {
        data = vector<T>(N + 1);
        this->N = N;
    }

    void add_at(int idx, T val) {
        for (int i = idx + 1; i <= N; i += (i & (-i))) {
            data[i] += val;
        }
    }

    T sum_to(int idx) {
        T res = 0;
        for (int i = idx + 1; i > 0; i -= (i & (-i))) {
            res += data[i];
        }
        return res;
    }

    T sum_in(int l, int r) { // [l, r]
        return sum_to(r) - sum_to(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q; 
    cin >> N >> Q;

    vector<int> C(N, -1);
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }

    vector<vector<tuple<int, int, int>>> queries(N);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        queries[r].push_back(tuple<int, int, int>(l, r, i));
    }

    auto bit = BIT<int>(N);
    auto V = *max_element(C.begin(), C.end());
    auto last = vector<int>(V + 1, -1);
    auto ans = vector<int>(Q, -1);

    for (int i = 0; i < N; i++) {
        if (last[C[i]] != -1) {
            bit.add_at(last[C[i]], -1);
        }

        bit.add_at(i, +1);
        last[C[i]] = i;

        for (auto& [l, r, idx] : queries[i]) {
            ans[idx] = bit.sum_in(l, r);
        }
    }

    for (auto x: ans) {
        cout << x << endl;
    }

    return 0;
}