#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 = 5 * (1e6 + 10), M = 2e6 + 10;
int seg[N], inf = 1e9, ans[N], mx[N];
vector<pair<int, pair<int, 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], 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(x, y);
}
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, tt = 20;
cin >> op >> x >> y;
mx[i] = max(mx[i - 1], y);
if (op == 'D')
tt = 10;
v.pb({y, {-i, {tt, x}}});
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)
{
i.S.F *= (-1);
if (i.S.S.F == 20)
{
upd(1, 0, M, i.S.S.S, i.F);
continue;
}
int tmp = solve(1, 1, i.S.S.S + 1, 0, M);
ans[i.S.F] = tmp;
}
for (auto i : Q)
cout << (ans[i] > mx[i] ? -1 : ans[i]) << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
23896 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
24344 KB |
Output isn't correct |
| 4 |
Incorrect |
92 ms |
32020 KB |
Output isn't correct |
| 5 |
Incorrect |
83 ms |
31624 KB |
Output isn't correct |
| 6 |
Incorrect |
85 ms |
31992 KB |
Output isn't correct |
| 7 |
Incorrect |
87 ms |
31992 KB |
Output isn't correct |
