# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
79825 | pzdba | Deda (COCI17_deda) | C++14 | 175 ms | 3656 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;
typedef pair<int, int> pii;
const int N = 200000;
int st[4*N+5];
void update(int n, int s, int e, int idx, int v){
if(s == e) st[n] = v;
else{
int mid = (s+e)/2;
if(idx <= mid) update(n+n, s, mid, idx, v);
else update(n+n+1, mid+1, e, idx, v);
st[n] = min(st[n+n], st[n+n+1]);
}
}
int query(int n, int s, int e, int l, int r, int y){
if(s > r || l > e) return 2e9;
if(st[n] > y) return 2e9;
if(s == e) return s;
int mid = (s+e)/2;
int q1 = query(n+n, s, mid, l, r, y);
if(q1 != 2e9) return q1;
int q2 = query(n+n+1, mid+1, e, l, r, y);
return q2;
}
int main(){
int n, q;
scanf("%d%d", &n, &q);
for(int i=1;i<=n;i++) update(1, 1, n, i, 2e9);
for(int i=1;i<=q;i++){
char s[2];
int x, a;
scanf("%s%d%d", s, &x, &a);
if(s[0] == 'M'){
update(1, 1, n, a, x);
}
else{
int y = x, b = a;
int ans = query(1, 1, n, b, n, y);
if(ans == 2e9) ans = -1;
printf("%d\n", ans);
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |