# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
870162 | vjudge1 | Deda (COCI17_deda) | C++17 | 103 ms | 12372 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;
struct query {
char c;
int x, y;
};
const int N = 2e5 + 10;
query q[N];
vector<int> node;
pair<int, int> child[N];
int n, m, cnt = 1, id[N], id1[4 * N], sg[4 * N];
void build(int v, int l, int r) {
if (l == r) {
id[l] = v;
id1[v] = l;
return;
}
int mid = (l + r) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
}
void update(int i, int x) {
int v = id[i];
sg[v] = x;
v /= 2;
while (v != 0) {
sg[v] = min(sg[2 * v], sg[2 * v + 1]);
v /= 2;
}
}
void get(int v, int i, int j, int l, int r) {
if (i > r || j < l) {
return;
}
if (i >= l && j <= r) {
node.push_back(v);
return;
}
int mid = (i + j) / 2;
get(2 * v, i, mid, l, r);
get(2 * v + 1, mid + 1, j, l, r);
}
void add(int a, int x) {
int i = lower_bound(child + 1, child + cnt, make_pair(a, x)) - child;
update(i, x);
}
int find_ans(int v, int y) {
if (id1[v] != 0) {
return id1[v];
}
if (sg[2 * v] <= y) {
return find_ans(2 * v, y);
}
else {
return find_ans(2 * v + 1, y);
}
}
void find(int b, int y) {
int l = 0, r = cnt;
while (r - l > 1) {
int mid = (l + r) / 2;
if (child[mid].first >= b) {
r = mid;
}
else {
l = mid;
}
}
node.clear();
get(1, 1, cnt - 1, r, cnt - 1);
bool flag = false;
for (int i = 0; i < node.size(); i++) {
if (sg[node[i]] <= y) {
flag = true;
int k = find_ans(node[i], y);
cout << child[k].first << "\n";
break;
}
}
if (!flag) {
cout << -1 << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> q[i].c >> q[i].x >> q[i].y;
if (q[i].c == 'M') {
child[cnt] = {q[i].y, q[i].x};
cnt++;
}
}
sort(child + 1, child + cnt);
memset(sg, 63, sizeof sg);
build(1, 1, cnt - 1);
for (int i = 0; i < m; i++) {
char c = q[i].c;
int x = q[i].x, y = q[i].y;
if (c == 'M') {
add(y, x);
}
else {
find(y, x);
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |