답안 #922136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922136	2024-02-05T06:44:03 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	110 ms	22100 KB

deda

#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

#	결과	실행 시간	메모리	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