# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
490310 | lto5 | Deda (COCI17_deda) | C++14 | 115 ms | 6864 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
const int INF = INT_MAX;
int st[MAX_N << 2];
void update(int id, int l, int r, int i, int val){
if(i < l || r < i)
return;
if(l == r){
st[id] = val;
return;
}
int m = l + r >> 1;
update(id << 1, l, m, i, val);
update(id << 1 | 1, m + 1, r, i, val);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if(r < u || v < l)
return INF;
if(u <= l && r <= v)
return st[id];
int m = l + r >> 1;
return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
void build(int id, int l, int r){
if(l == r){
st[id] = INF;
return;
}
int m = l + r >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
// walk on segment tree
int query(int id, int l, int r, int lowerbound, int k){
if(st[id] > k)
return -1;
if(r < lowerbound)
return -1;
if(l == r)
return l;
int m = l + r >> 1;
int res = -1;
if(st[id << 1] <= k)
res = query(id << 1, l, m, lowerbound, k);
if(res == -1)
res = query(id << 1 | 1, m + 1, r, lowerbound, k);
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
build(1, 1, n);
while(q--){
char type;
cin >> type;
if(type == 'M'){
int x, a;
cin >> x >> a;
update(1, 1, n, a, x);
}
else{
int y, b;
cin >> y >> b;
cout << query(1, 1, n, b, y) << '\n';
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |