Submission #954255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954255	2024-03-27T14:21:11 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	101 ms	7848 KB

deda

#include <bits/stdc++.h>
using namespace std;
#define ishowspeed ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define MXN 200055
#define cl(x) (x<<1)
#define cr(x) (x<<1)+1
int seg[MXN*4+5],arr[MXN];
int searchb = 1e18;
int ansl = 1e18;
int query(int id,int l,int r,int sl,int sr){
    if(sl<=l&&r<=sr) {
        if(seg[id] > searchb) return seg[id];
        else{
            if(l == r) {
                ansl = min(ansl,l);
                return seg[id];
            }
        }
    }
    int mid=(l+r)>>1,res=1e18;
    if(sl<=mid){
        int x = query(cl(id),l,mid,sl,sr);
        res = min(res,x);
        if(x <= searchb) return res;
    } 
    if(mid<sr){
        int x = query(cr(id),mid+1,r,sl,sr);
        res = min(res,x);
    }  
    return res;
}
void pull(int id){
    seg[id] = min(seg[cl(id)] , seg[cr(id)]);
}
void update(int id,int l,int r,int x,int v){
    if(l==r){
        seg[id] = v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        update(cl(id),l,mid,x,v);    
    }
    if(mid<x){
        update(cr(id),mid+1,r,x,v);  
    }
    pull(id);
}
void build(int id,int l,int r){
    if(l==r){
        seg[id]=arr[l];
        return;
    }
    int mid=(l+r)>>1;
    build(cl(id),l,mid);
    build(cr(id),mid+1,r);
    pull(id);
}
signed main(){
    ishowspeed
    int n,q,x,L,R;
    cin >> n >> q;
    L = 1;
    R = n;
    for(int i = 1;i <= n;i++) arr[i] = 1e18;
    build(1,L,R);
    char o;
    int a,b;
    while(q--){
        cin >> o >> a >> b;
        if(o == 'M') update(1,L,R,b,a);
        else {
            searchb = a;
            ansl = 1e18;
            int rs = query(1,1,R,b,R);
            if(rs <= searchb) cout << ansl << '\n';
            else cout <<  "-1\n";
        }
    }
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:62:13: warning: unused variable 'x' [-Wunused-variable]
   62 |     int n,q,x,L,R;
      |             ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	2 ms	2552 KB	Output is correct
4	Correct	101 ms	7848 KB	Output is correct
5	Correct	76 ms	5456 KB	Output is correct
6	Correct	79 ms	7508 KB	Output is correct
7	Correct	84 ms	7764 KB	Output is correct