Submission #1084738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084738	2024-09-06T20:49:26 Z	vanillaPlayer	Deda (COCI17_deda)	C++17	20 / 140	1000 ms	6992 KB

deda

#include <bits/stdc++.h>

using namespace std;

#define fori(i,n) for(int i = 0; i < (n);i++)
#define fora(i,a,n) for(int i = (a); i <= (n);i++)
#define MAX_N 2000005
const int INF = 1e9 + 7;
#define fill(a, v) memset(a, (long long)v, sizeof(a))
#define oper max
#define ll long long

int sgt[4*(MAX_N)];
int n,q,nn;

void build(int v, int tl, int tr){

    if(tl == tr){
        sgt[v] = INF;
        
    }else{
        int tm = (tl+tr)/2;
        build(v*2, tl, tm);
        build(v*2+1, tm + 1, tr);
    }

}

void update(int v, int tl, int tr, int pos, int new_value){

    if(tl == tr){
        sgt[v] = new_value;
        
    }else{
        int tm  = (tl+tr)/2;

        if(pos <= tm){
            update(v*2, tl, tm, pos, new_value);
        }else{
            update(v*2+1, tm+1, tr, pos, new_value);
        }
        sgt[v] = min(sgt[v*2], sgt[v*2+1]);
    }

}

int query(int v, int tl , int tr, int l, int r){

    if(l > r){
        return INF;
    }    
    if( l == tl && r == tr){
        return sgt[v];
    }else{
        int tm = (tl+tr)/2;
        int leftAns = query(2*v, tl, tm, l, min(tm, r));
        int rightAns = query(2*v + 1, tm+1, tr, max(l, tm+1), r);
        return min(leftAns, rightAns);
    }


}



int main(){

    cin >> n >> q;
    build(1,0,n-1);

    while(q--){
        char id;
        cin >> id;
        if(id == 'M'){
            int a, x;
            cin >> x >> a;
            update(1, 0, n-1,a-1, x);
        }else{
            int b, y;
            cin >> y >> b;
            int l = b - 1, r = n - 1, ans = n + 1;
            while(l <= r){
                int child  = (l+r)/2;
                int min_stop = query(1,0,n-1,l,child);    
                if(min_stop <= y){
                    ans = min(ans,child);
                    r = child - 1;
                }else{
                    l = child + 1;
                }
            }

            if(ans == n + 1)
                cout << "-1\n";
            else
                cout << ans + 1 << "\n";

        }

    }

}

Subtask #1

20.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	10 ms	520 KB	Output isn't correct
4	Execution timed out	1032 ms	6992 KB	Time limit exceeded
5	Incorrect	611 ms	5712 KB	Output isn't correct
6	Incorrect	716 ms	6740 KB	Output isn't correct
7	Incorrect	796 ms	6860 KB	Output isn't correct