oj.uz

Submission #40199

# Submission time Handle Problem Language Result Execution time Memory
40199 2018-01-29T17:41:43 Z evpipis Deda (COCI17_deda) C++
100 / 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;
}

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

    while (q--){
        char tp;
        int a, x;
        scanf(" %c %d %d", &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:45:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
deda.cpp:52:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &tp, &x, &a);
                                        ^

Subtask #1
100.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 731 ms 5144 KB Output is correct
6 Correct 881 ms 5144 KB Output is correct
7 Execution timed out 1000 ms 5144 KB Execution timed out