oj.uz

Submission #379161

# Submission time Handle Problem Language Result Execution time Memory
379161 2021-03-17T11:26:26 Z FatihSolak Deda (COCI17_deda) C++17
140 / 140
 527 ms 4580 KB 
#include <bits/stdc++.h>
#define N 200005
#define K 20
#define INF 1000000005
using namespace std;
int t[4*N];
void upd(int v,int l,int r,int pos,int val){
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l+r)/2;
    if(pos<=m){
        upd(v*2,l,m,pos,val);
    }
    else{
        upd(v*2+1,m+1,r,pos,val);
    }
    t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r,int val){
    if(tr < l || r < tl)return -1;
    if(t[v] > val)return -1;
    if(tl == tr)return tl;
    int tm = (tl+tr)/2;
    int tmp = get(v*2,tl,tm,l,r,val);
    if(tmp != -1){
        return tmp;
    }
    return get(v*2+1,tm+1,tr,l,r,val);
}
void solve(){
    int n,q;
    cin >> n >> q;
    for(int i=0;i<4*N;i++)t[i] = INF;
    for(int i=0;i<q;i++){
        char a;
        int b,c;
        cin >> a >> b >> c;
        if(a == 'M'){
            upd(1,1,n,c,b);
        }
        if(a == 'D'){
            cout << get(1,1,n,c,n,b) << endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 15 ms 3436 KB Output is correct
4 Correct 527 ms 4580 KB Output is correct
5 Correct 390 ms 4204 KB Output is correct
6 Correct 441 ms 4460 KB Output is correct
7 Correct 458 ms 4460 KB Output is correct