# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
876663 | vjudge1 | Deda (COCI17_deda) | C++17 | 105 ms | 29352 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;
#define ll long long int
#define F first
#define S second
#define pb push_back
const int N = 4 * (1e6 + 10), M = 1e6 + 10;
int seg[N], inf = 1e9, ans[N];
vector<pair<int, pair<char, pair<int, int>>>> v;
void upd(int id, int s, int e, int i, int x)
{
if (i == s && i == e - 1)
{
seg[id] = min(seg[id], x);
return;
}
if (i < s || i >= e)
return;
int mid = (s + e) / 2;
upd(id * 2, s, mid, i, x);
upd(id * 2 + 1, mid, e, i, x);
seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}
int solve(int id, int l, int r, int s, int e)
{
// cout << id << " " << s << " " << e << " " << i << "\n";
if (l <= s && e <= r)
return seg[id];
if (r <= s || l >= e)
return inf;
int mid = (s + e) / 2;
int x = solve(id * 2, l, r, s, mid);
int y = solve(id * 2 + 1, l, r, mid, e);
return min(min(x, y), inf);
}
int main()
{
ios_base::sync_with_stdio(false),cin.tie(0);
for (int i = 0; i < N; i ++)
seg[i] = inf;
int n, q;
cin >> n >> q;
vector<int> Q;
for (int i= 1; i <= q; i ++)
{
char op;
int x, y;
cin >> op >> x >> y;
v.pb({y, {op, {-x, -i}}});
if (op == 'D')
Q.pb(i);
}
sort(v.begin(), v.end()); reverse(v.begin(), v.end());
// for (auto i : v)
// cout << i.F <<" " << i.S.F << " " << i.S.S.F << " " << i.S.S.S << "\n";
// for (auto i : v)
for (auto i : v)
{
i.S.S.F *= (-1), i.S.S.S *= (-1);
if (i.S.F == 'M')
{
upd(1, 0, M, i.S.S.F, i.F);
continue;
}
int tmp = solve(1, 1, i.S.S.F + 1, 0, M);
ans[i.S.S.S] = tmp;
}
for (auto i : Q)
cout << (ans[i] == inf ? -1 : ans[i]) << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |