Submission #954248

#	Time	Username	Problem	Language	Result	Execution time	Memory
954248		vjudge1	Deda (COCI17_deda)	C++17	0 / 140	393 ms	11208 KiB

deda

#include <bits/stdc++.h>
using namespace std;
#define ishowspeed ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define MXN 200005
#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)
        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){
        //     ansl = min(ansl,l);
        // }
    } 
    if(mid<sr){
        int x = query(cr(id),mid+1,r,sl,sr);
        res = min(res,x);
        // if(x <= searchb){
        //     ansl = min(ansl,mid+1);
        // }
    }  
    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){
        if(seg[id] == 1e18) seg[id] = v;
        else 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(){
    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);
    // for(int i = 0; i < 50;i++){
    //     cout << seg[i]<<' ';
    // }
    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 << rs << '\n';
                cout << ansl << '\n';
            }
            else cout <<  "-1\n";
        }
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 140