# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
479668 | aris12345678 | Deda (COCI17_deda) | C++14 | 819 ms | 8644 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 long long ll;
typedef pair<int, int> pii;
#define X first
#define Y second
const int mxN = 200005;
int st[4*mxN], a[mxN];
void update(int p, int l, int r, int i, int v) {
if(l == r)
st[p] = v;
else {
int md = (l+r)/2;
if(i <= md)
update(2*p, l, md, i, v);
else
update(2*p+1, md+1, r, i, v);
st[p] = min(st[2*p], st[2*p+1]);
}
}
int Min(int p, int l, int r, int i, int j) {
if(i > r || l > j)
return INT_MAX;
if(i <= l && r <= j)
return st[p];
int md = (l+r)/2;
return min(Min(2*p, l, md, i, j), Min(2*p+1, md+1, r, i, j));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
scanf("%d %d\n", &n, &q);
fill(st, st+4*mxN, INT_MAX);
fill(a, a+n, INT_MAX);
while(q--) {
char type;
int l, r;
cin >> type >> l >> r;
if(type == 'M') {
update(1, 1, n, r, l);
a[r] = l;
} else {
int st = r, en = n, md, ans = -1;
while(st <= en) {
md = (st+en)/2;
// cout << st << " " << md << " " << a[md] << " " << en << " " << ans << "\n";
if(md-1 >= r && Min(1, 1, n, r, md-1) <= l)
en = md-1;
else if(a[md] <= l) {
ans = md;
break;
} else
st = md+1;
}
printf("%d\n", ans);
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |