oj.uz

Submission #272832

# Submission time Handle Problem Language Result Execution time Memory
272832 2020-08-18T15:57:03 Z rqi Deda (COCI17_deda) C++14
140 / 140
 835 ms 6904 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(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(){
    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 2304 KB Output is correct
2 Correct 4 ms 2304 KB Output is correct
3 Correct 18 ms 2432 KB Output is correct
4 Correct 835 ms 6904 KB Output is correct
5 Correct 650 ms 6456 KB Output is correct
6 Correct 739 ms 6776 KB Output is correct
7 Correct 768 ms 6904 KB Output is correct