oj.uz

Submission #922136

# Submission time Handle Problem Language Result Execution time Memory
922136 2024-02-05T06:44:03 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 110 ms 22100 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Segtree{
    int n, tl, tr, val;
    using T = array<int, 2>;
 
    T base = {(int)1e9, (int)1e9};
    vector<T> arr;
 
    T merge(const T &x, const T &y){
        return min(x, y);
    }
     T merge2(const T &x, const T &y){
        if(x[0]!=1e9) return x;
        return y;
    }
    Segtree(int n) : n(n), arr(4*n, base) {}
 
    void update(int v, int l, int r, int pos, T val){
        if(l==r) arr[v] = val;
        else{
            int mid = (l+r) / 2;
            if(pos<=mid) update(v*2, l, mid, pos, val);
            else update(v*2+1, mid+1, r, pos, val);

            arr[v] = merge(arr[v*2], arr[v*2+1]);
        }
    
    }
    void update(int pos, T val){
        update(1, 0, n-1, pos, val);
    }
    T get(int v, int l, int r){
        if(l> tr || r < tl) return base;
       // cout<<l<<" "<<r<<"aa\n";
       // cout<<arr[v][0]<<" "<<arr[v][1]<<"\n";
        if(l>=tl && r<= tr){
            if(l==r) return arr[v];
            else if(arr[v][0] <= val){
                int mid = (l+r) /2;
                if(arr[v*2][0] <= val) return get(v*2, l, mid);
                else return get(v*2+1, mid+1, r);
            }
            return base;
        }
        else{
           // if(l==r) return base;
            int mid = (l+r) /2;
            auto a = get(v*2, l, mid);

            if(a[0]>val) return get(v*2+1, mid+1, r);
            return a;
        }
    }

    T operator()(int l, int r, int v){
        tl = l; tr = r; val = v;
        return get(1, 0, n-1);

    }


}; 





signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; cin >> n >> q;

    vector<array<int, 3>> qu(q);

    for(int i=0;i<q; i++){
        char x; int y, z, a;
        cin >> x >> y >> z;
        z--;
        a=(x=='M')?0:1;

        qu[i] ={y, a, z};
    }

   /* vector<int> id(q), pos(q);
    iota(id.begin(), id.end(), 0);

    /*sort(id.begin(), id.end(), [&](int &i, int &j){
        return qu[i]<qu[j];
    });


    for(int i=0; i<q; i++){
        pos[id[i]] = i;
    }*/

    Segtree st(n);

    for(int i=0; i<q; i++){
        auto [x, t, y] = qu[i];
        if(t==0){
            st.update(y, {x, y});
        }
        else{

            auto val =st(y, n-1, x);
            //cout<<val[0]<<" "<<val[1]<<"\n";
            if(val[0] > x) cout<<-1<<"\n";
            else cout<<val[1]+1 <<"\n";

        }
    }
 //   cout<<"heh";


}

Compilation message

deda.cpp:91:5: warning: "/*" within comment [-Wcomment]
   91 |     /*sort(id.begin(), id.end(), [&](int &i, int &j){
      |

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 102 ms 22100 KB Output is correct
5 Correct 88 ms 15436 KB Output is correct
6 Correct 91 ms 18688 KB Output is correct
7 Correct 110 ms 22100 KB Output is correct