Submission #861440

#	Time	Username	Problem	Language	Result	Execution time	Memory
861440		Rareshika	Deda (COCI17_deda)	C++14	140 / 140	82 ms	6844 KiB

deda

#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 (stderr)

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 / 140