| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 876672 |
2023-11-22T08:02:17 Z |
vjudge1 |
Deda (COCI17_deda) |
C++17 |
|
91 ms |
25224 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<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 * 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, tt = 10;
cin >> op >> x >> y;
if (op == 'D')
tt = 20;
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.S.S *= (-1), i.S.F *= (-1);
if (i.S.S.F == 10)
{
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] == inf ? -1 : ans[i]) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
17124 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
17244 KB |
Output isn't correct |
| 4 |
Incorrect |
91 ms |
25224 KB |
Output isn't correct |
| 5 |
Incorrect |
88 ms |
24900 KB |
Output isn't correct |
| 6 |
Incorrect |
84 ms |
25100 KB |
Output isn't correct |
| 7 |
Incorrect |
86 ms |
25080 KB |
Output isn't correct |
