oj.uz

Submission #861440

# Submission time Handle Problem Language Result Execution time Memory
861440 2023-10-16T07:53:51 Z Rareshika Deda (COCI17_deda) C++14
140 / 140
 82 ms 6844 KB 
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;

int N, Q;

struct SegTree
{
    int next_power_of_two(int n)
    {
        int p = 1;
        while (p <= n)
            p <<= 1;
        return p;
    }
    
    int offset;
    vector <int> data;
    
    SegTree(int n)
    {
        offset = next_power_of_two(n);
        
        data.resize(2 * offset);
        
        for (int i = 0 ; i < data.size() ; ++ i)
            data[i] = INF;
    }
    
    void _update(int node, int l, int r, int pos, int val)
    {
        if (l == r)
        {
            data[node] = val;
            return;
        }
        
        int mid = (l + r) / 2;
        
        if (pos <= mid)
            _update(2 * node, l, mid, pos, val);
        else
            _update(2 * node + 1, mid + 1, r, pos, val);
            
        int val_st = (data[2 * node] == 0) ? INF : data[2 * node];
        int val_dr = (data[2 * node + 1] == 0) ? INF : data[2 * node + 1];
        
        data[node] = min(val_st, val_dr);
    }
    
    inline void update(int pos, int val)
    {
        _update(1, 1, offset, pos, val);
    }
    
    int _query(int node, int l, int r, int ql, int stop_max)
    {
        if (r < ql)
            return -1;
            
        if (data[node] > stop_max)
            return -1;
        
        if (l == r)
            return r;
            
        int mid = (l + r) / 2;
        int rasp_st = _query(2 * node, l, mid, ql, stop_max);
        
        if (rasp_st != -1)
        {
            return rasp_st;
        }
            
        int rasp_dr = _query(2 * node + 1, mid + 1, r, ql, stop_max);
        return rasp_dr;
    }
    
    int query(int ql, int stop_max)
    {
        return _query(1, 1, offset, ql, stop_max);
    }
};



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> Q;
    
    SegTree st = SegTree(N + 1);
        
    char op;
    int a, b;
    while (Q --)
    {
        cin >> op >> a >> b;
        
        if (op == 'M')
        {
            st.update(b, a);
        }
        else
        {
            cout << st.query(b, a) << "\n";
        }
    }
    
    return 0;
}

Compilation message

deda.cpp: In constructor 'SegTree::SegTree(int)':
deda.cpp:28:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0 ; i < data.size() ; ++ i)
      |                          ~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 66 ms 6844 KB Output is correct
5 Correct 82 ms 5480 KB Output is correct
6 Correct 70 ms 6624 KB Output is correct
7 Correct 72 ms 6840 KB Output is correct