#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005
#define X (1<<20)
using pt = complex<ll>;
ll dot(pt a, pt b) { return (conj(a) * b).real(); }
ll at(pt a, ll x) { return dot(a, {x, 1}); }
pt t[X<<1];
int n;
array<int, 2> a[N], b[N];
void add(pt k, int v = 0, int l = 1, int r = (X-1))
{
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2, L = at(k, l) <= at(t[v], l), M = at(k, m) <= at(t[v], m);
if (M) swap(t[v], k);
if (l == r) return;
if (L != M) add(k, vl, l, m);
else add(k, vr, m+1, r);
}
ll qry(ll x, int v = 0, int l = 1, int r = (X-1))
{
ll here = at(t[v], x);
if (l == r) return here;
int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
if (x <= m) return min(here, qry(x, vl, l, m));
return min(here, qry(x, vr, m+1, r));
}
int main()
{
ShinLena;
cin >> n;
for (int i = 0; i * sizeof *t < sizeof t; ++i) t[i] = {0, ll(1e15)};
for (int i = 1; i <= n; ++i) cin >> a[i][0] >> a[i][1], b[i] = a[i];
sort(b+1, b+n+1, greater<array<int, 2>>());
{
int j = 1, hi_height = 0;
for (int i = 1; i <= n; ++i)
{
if (b[i][1] <= hi_height);
else a[j++] = b[i], hi_height = b[i][1];
}
n = j - 1;
}
ll dp = 0;
for (int i = 1; i <= n; ++i) add({a[i][0], dp}), dp = qry(a[i][1]);
cout << dp;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
36188 KB |
Memory limit exceeded |
2 |
Runtime error |
6 ms |
36076 KB |
Memory limit exceeded |
3 |
Runtime error |
16 ms |
36416 KB |
Memory limit exceeded |
4 |
Runtime error |
18 ms |
36420 KB |
Memory limit exceeded |
5 |
Runtime error |
21 ms |
37208 KB |
Memory limit exceeded |
6 |
Runtime error |
25 ms |
36184 KB |
Memory limit exceeded |
7 |
Runtime error |
19 ms |
36188 KB |
Memory limit exceeded |
8 |
Runtime error |
26 ms |
36188 KB |
Memory limit exceeded |
9 |
Runtime error |
25 ms |
36440 KB |
Memory limit exceeded |
10 |
Runtime error |
25 ms |
36304 KB |
Memory limit exceeded |