oj.uz

Submission #61619

# Submission time Handle Problem Language Result Execution time Memory
61619 2018-07-26T08:13:29 Z win11905 Deda (COCI17_deda) C++11
140 / 140
 208 ms 17240 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1<<18;
const int INF = 1e9;

int n, m, t[N<<1];

void update(int x, int v) {
    for(t[x += N] = v; x != 1; x >>= 1) t[x>>1] = min(t[x], t[x^1]); 
}

int query(int x, int v, int p = 1, int l = 0, int r = N - 1) {
    if(t[p] > v) return INF;
    if(l == r) return l;
    int m = l + r >> 1;
    if(x <= m) {
        int z = query(x, v, p<<1, l, m);
        if(z != INF) return z;
    }
    if(x <= r) {
        int z = query(x, v, p<<1|1, m+1, r);
        if(z != INF) return z;
    }
    return INF;
}

int main() {
    fill_n(t, N<<1, INF);
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        char c; int a, b; scanf(" %c %d %d", &c, &a, &b);
        if(c == 'M') update(b, a);
        else {
            int ret = query(b, a);
            printf("%d\n", ret == INF ? -1 : ret);
        }
    }
}

Compilation message

deda.cpp: In function 'int query(int, int, int, int, int)':
deda.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
deda.cpp: In function 'int main()':
deda.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:32:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         char c; int a, b; scanf(" %c %d %d", &c, &a, &b);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 7 ms 2424 KB Output is correct
3 Correct 8 ms 2536 KB Output is correct
4 Correct 208 ms 7104 KB Output is correct
5 Correct 137 ms 10024 KB Output is correct
6 Correct 168 ms 13788 KB Output is correct
7 Correct 166 ms 17240 KB Output is correct