oj.uz

Submission #40202

# Submission time Handle Problem Language Result Execution time Memory
40202 2018-01-29T17:58:42 Z evpipis Deda (COCI17_deda) C++
140 / 140
 931 ms 5144 KB 
#include <bits/stdc++.h>
using namespace std;

const int len = 2e5+5, inf = 1e9+5;
int tree[4*len], n;

void update(int p, int l, int r, int i, int v){
    if (l == r)
        tree[p] = v;
    else{
        int mid = (l+r)>>1;
        if (i <= mid) update(2*p, l, mid, i, v);
        else update(2*p+1, mid+1, r, i, v);
        tree[p] = min(tree[2*p], tree[2*p+1]);
    }
}

int query(int p, int l, int r, int i, int j){
    if (i <= l && r <= j)
        return tree[p];
    //if (r < i || j < l)
      //  return inf;
    int mid = (l+r)>>1;
    if (j <= mid) return query(2*p, l, mid, i, j);
    if (i > mid) return query(2*p+1, mid+1, r, i, j);
    return min(query(2*p, l, mid, i, j), query(2*p+1, mid+1, r, i, j));
}

int bs(int b, int y){
    int l = b, r = n, ans = -1;
    while (l <= r){
        int mid = (l+r)>>1;
        if (query(1, 1, n, b, mid) <= y){
            ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }

    return ans;
}

inline void read(int &res){
    char c;
    while (c = getchar(), c < '0' || c > '9'){}

    res = c-'0';
    while (c = getchar(), c >= '0' && c <= '9')
        res = 10*res+c-'0';
}

int main(){
    int q;
    read(n), read(q);
    //printf("%d, %d\n", n, q);
    for (int i = 1; i <= 4*n; i++)
        tree[i] = inf;

    while (q--){
        char tp;
        int a, x;
        //scanf(" %c", &tp);
        while (tp = getchar(), tp != 'M' && tp != 'D'){}
        read(x), read(a);
        //printf("%c %d %d\n", tp, x, a);
        if (tp == 'M')
            update(1, 1, n, a, x);
        else
            printf("%d\n", bs(a, x));
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5144 KB Output is correct
2 Correct 0 ms 5144 KB Output is correct
3 Correct 6 ms 5144 KB Output is correct
4 Correct 931 ms 5144 KB Output is correct
5 Correct 526 ms 5144 KB Output is correct
6 Correct 610 ms 5144 KB Output is correct
7 Correct 713 ms 5144 KB Output is correct