Submission #97823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97823	2019-02-18T18:06:12 Z	dalgerok	Deda (COCI17_deda)	C++17	140 / 140	151 ms	6876 KB

deda

#include<bits/stdc++.h>
using namespace std;


const int N = 2e5 + 5, INF = 2e9;



int n, m, t[4 * N];


void update(int v, int l, int r, int pos, int val){
    if(l == r){
        t[v] = val;
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, val);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, val);
    }
    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int tl, int tr, int val){
    if(l > r || l > tr || tl > r || t[v] > val){
        return -1;
    }
    if(l == r){
        return l;
    }
    int mid = (r + l) >> 1;
    int x = get(v + v, l, mid, tl, tr, val);
    if(x == -1){
        x = get(v + v + 1, mid + 1, r, tl, tr, val);
    }
    return x;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        update(1, 1, n, i, INF);
    }
    while(m--){
        char c;
        cin >> c;
        if(c == 'M'){
            int x, y;
            cin >> x >> y;
            update(1, 1, n, y, x);
        }
        else{
            int x, y;
            cin >> x >> y;
            cout << get(1, 1, n, y, n, x) << "\n";
        }
    }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	126 ms	6876 KB	Output is correct
5	Correct	126 ms	5368 KB	Output is correct
6	Correct	136 ms	6652 KB	Output is correct
7	Correct	151 ms	6776 KB	Output is correct