oj.uz

Submission #40200

# Submission time Handle Problem Language Result Execution time Memory
40200 2018-01-29T17:50:58 Z evpipis Deda (COCI17_deda) C++
120 / 140
 1000 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)/2;
        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)/2;
    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)/2;
        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;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:62:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &tp);
                          ^

Subtask #1
120.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5144 KB Output is correct
2 Correct 1 ms 5144 KB Output is correct
3 Correct 8 ms 5144 KB Output is correct
4 Execution timed out 1000 ms 5144 KB Execution timed out
5 Correct 698 ms 5144 KB Output is correct
6 Correct 867 ms 5144 KB Output is correct
7 Correct 934 ms 5144 KB Output is correct