Submission #975740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975740	2024-05-05T19:50:47 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	742 ms	11028 KB

deda

#include <bits/stdc++.h>
#define MAXN 200005
#define MOD 998244353
using namespace std;

typedef long long ll;

ll st[4*MAXN], ar[MAXN],n,k,a,b,c,d;

void build(int pos, int l, int r){
    //cout << "aqui2\n";
    if(l == r){
        st[pos] = 1e17;
        return;
    }
    int m = (l+r)/2;

    build(pos*2, l,m);
    build(pos*2 +1, m+1,r);
    st[pos] = min(st[pos*2], st[pos*2 + 1]);

    return;
}

void update(int pos, int indice, int valor, int l, int r){
    //cout << "aqui\n";
    if(l == r){
        st[pos] = valor;
        return;
    }
    int m = (l+r)/2;

    if(indice <= m)update(pos*2, indice, valor, l,m);
    else update(pos*2 + 1, indice, valor, m+1,r);

    st[pos] = min(st[pos*2], st[pos*2 + 1]);
    return;
}

ll query(int pos, int l, int r, int lq, int rq){
    
    if(l >= lq && r <= rq){
        return st[pos];
    }
    if(l > rq || r < lq){
        return 1e17;
    }
    int m = (l+r)/2;
    return min(query(pos*2, l,m,lq,rq), query(pos*2 + 1, m+1,r,lq,rq));
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;

    
    build(1,1,n);

    char op;
    for(int i =0; i < k; i++){
        cin >> op;
        if(op == 'M'){
            cin >> b >> c;
            //cout << "entra\n";
            update(1,c,b,1,n);
        }else{
            //cout << "query " << '\n';
            cin >> a >> b;
            int ini = b, fin = n;
            int res = -1;
            
            while(ini <= fin){
              
                int mitad = (ini + fin)/2;
                if(query(1,1,n,ini,mitad) <= a){
                    fin = mitad - 1;
                    res = mitad;
                }else ini = mitad + 1;
            }
            cout << res << '\n';
        }
    }
   
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	7 ms	2396 KB	Output is correct
4	Correct	742 ms	11028 KB	Output is correct
5	Correct	470 ms	8592 KB	Output is correct
6	Correct	559 ms	11020 KB	Output is correct
7	Correct	661 ms	11012 KB	Output is correct