oj.uz

Submission #869061

# Submission time Handle Problem Language Result Execution time Memory
869061 2023-11-03T04:22:43 Z sleepntsheep Harbingers (CEOI09_harbingers) C++17
0 / 100
 26 ms 37208 KB 
#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;
}

Subtask #1
0 / 100.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