# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
234431 | NONAME | Deda (COCI17_deda) | C++17 | 120 ms | 3704 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>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef long double ld;
int n, q;
int t[8 * N];
void build(int v, int l, int r) {
t[v] = 2e9;
if (l >= r)
return;
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
}
void upd(int v, int l, int r, int ps, int vl) {
if (l == r) {
t[v] = vl;
return;
}
int md = (l + r) >> 1;
if (ps <= md) upd(v + v, l, md, ps, vl);
else upd(v + v + 1, md + 1, r, ps, vl);
t[v] = min(t[v + v], t[v + v + 1]);
}
int f(int v, int l, int r, int tl, int tr, int vl) {
if ((l > r) || (tl > r) || (l > tr) || (t[v] > vl))
return -1;
if (l == r)
return l;
int md = (l + r) >> 1;
int c = -1;
if (t[v + v] <= vl) c = f(v + v, l, md, tl, tr, vl);
if (c == -1)
c = f(v + v + 1, md + 1, r, tl, tr, vl);
return c;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("input.txt");
cin >> n >> q;
build(1, 0, n - 1);
while (q--) {
char c;
cin >> c;
if (c == 'D') {
int x, y;
cin >> x >> y;
y--;
int rs = f(1, 0, n - 1, y, n - 1, x);
cout << (rs == -1 ? -1 : rs + 1) << el;
}
if (c == 'M') {
int x, y;
cin >> x >> y;
y--;
upd(1, 0, n - 1, y, x);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |