oj.uz

Submission #272836

# Submission time Handle Problem Language Result Execution time Memory
272836 2020-08-18T16:00:56 Z rqi Deda (COCI17_deda) C++14
140 / 140
 103 ms 3516 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int SZ = 262144;

int seg[2*SZ];

void upd(int val, int pos){
    for(int i = pos+SZ; i >= 1; i/=2){
        seg[i] = min(seg[i], val);
    }
}

int query(int Y, int pos, int ind = 1, int L = 0, int R = SZ-1){
    if(R < pos) return -1;
    if(seg[ind] > Y) return -1;
    if(L == R){
        if(seg[ind] <= Y) return L;
        return -1;
    }
    if(pos <= L && seg[ind] > Y){
        return -1;
    }

    int M = (L+R)/2;
    int val = query(Y, pos, 2*ind, L, M);
    if(val != -1) return val;
    return query(Y, pos, 2*ind+1, M+1, R);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    for(int i = 1; i < 2*SZ; i++){
        seg[i] = MOD;
    }
    int N, Q;
    cin >> N >> Q;
    for(int i = 1; i <= Q; i++){
        char typ;
        cin >> typ;
        if(typ == 'M'){
            int X, A;
            cin >> X >> A;
            upd(X, A);
        }
        else{
            int Y, B;
            cin >> Y >> B;
            cout << (query(Y, B)) << "\n";
        }
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 4 ms 2432 KB Output is correct
4 Correct 91 ms 3516 KB Output is correct
5 Correct 95 ms 3192 KB Output is correct
6 Correct 97 ms 3320 KB Output is correct
7 Correct 103 ms 3448 KB Output is correct