Submission #272836

#	Time	Username	Problem	Language	Result	Execution time	Memory
272836		rqi	Deda (COCI17_deda)	C++14	140 / 140	103 ms	3516 KiB

deda

#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 / 140