제출 #869061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869061		sleepntsheep	Harbingers (CEOI09_harbingers)	C++17	0 / 100	26 ms	37208 KiB

harbingers

#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