| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876663 |
2023-11-22T07:49:52 Z |
vjudge1 |
Deda (COCI17_deda) |
C++17 |
|
105 ms |
29352 KB |
#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 |
| 1 |
Correct |
4 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
17136 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
17508 KB |
Output isn't correct |
| 4 |
Incorrect |
90 ms |
29144 KB |
Output isn't correct |
| 5 |
Incorrect |
81 ms |
28156 KB |
Output isn't correct |
| 6 |
Incorrect |
91 ms |
29352 KB |
Output isn't correct |
| 7 |
Incorrect |
105 ms |
28680 KB |
Output isn't correct |
