oj.uz

Submission #445805

# Submission time Handle Problem Language Result Execution time Memory
445805 2021-07-19T16:06:57 Z nickmet2004 Deda (COCI17_deda) C++11
140 / 140
 434 ms 7868 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n , q , a[N];
int T[1<<20] , S , A;
char B;

void upd(int id , int l = 0 , int r = n - 1 , int pos= 0){
    if(id < l || id > r) return;
    if(l == r){T[pos] = S; return;}
    int mid = (l + r) >>1;
    upd(id ,l , mid ,pos * 2 + 1);
    upd(id ,mid + 1 , r , pos * 2 + 2);
    T[pos] = min(T[pos * 2 + 1] ,T[pos * 2 + 2]);
}
int f(int L , int R , int l = 0 , int r = n - 1 , int pos = 0){
    if(R < l || r < L)return -1;
    if(L <= l && r <= R){
        if(T[pos] > S)return -1;
        while(l < r){
            int mid = (l + r) >>1;
            if(T[pos * 2 + 1] <= S) r= mid , pos = pos * 2 + 1;
            else pos = pos * 2 + 2 , l = mid+ 1;
        }return l;
    }
    int mid = (l + r) >> 1;
    int k = f(L , R , l , mid , pos * 2 + 1);
    if(k != -1)return k;
    return f(L , R , mid + 1 , r , pos * 2 + 2);
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for(int i = 0; i < 4 * N; ++i) T[i] = 2e9;
    while(q--){
        cin >> B >> S >> A; --A;
        if(B == 'M') upd(A);
        else {
            int x =f(A , n - 1);
            if(x != -1) cout << x + 1 << endl;
            else cout << x << endl;
        }
    }


}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 10 ms 3404 KB Output is correct
4 Correct 434 ms 7868 KB Output is correct
5 Correct 327 ms 7452 KB Output is correct
6 Correct 359 ms 7708 KB Output is correct
7 Correct 376 ms 7868 KB Output is correct