Description

题目链接

Solution

考虑模拟怎么做,每当遇见一架飞机,查询当前空余的廊桥有哪些。

由于是先到先得,还需要廊桥的编号最小。

因此只需要一个数据结构,支持查询这两个东西就行了。可以用 std::set 实现,或者我写了个线段树上二分。

然后打错了一个变量名,成功沦为暴力分。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template<class T>
void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))  { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Air {
    int l, r;
    friend bool operator < (const Air &a, const Air &b) {
        return a.l < b.l;
    }
} a[100010], b[100010];

struct Node {
    int l, r, v, id;
} t[800010];

int f1[100010], f2[100010], A1[200010], A2[200010];
int n, m1, m2, ans, cnt;

inline int lson(int x) { return x << 1; }
inline int rson(int x) { return x << 1 | 1; }

void buildTree(int x, int l, int r) {
    t[x].l = l, t[x].r = r;
    if (l == r)    {
        t[x].id = l;
        t[x].v = 1e9;
        return ;
    }
    int mid = (l + r) >> 1;
    buildTree(lson(x), l, mid), buildTree(rson(x), mid + 1, r);
}

void modify(int x, int p, int d) {
    if (t[x].l == t[x].r) {
        t[x].v = d;
        return ;
    }
    int mid = (t[x].l + t[x].r) >> 1;
    if (p <= mid)    modify(lson(x), p, d);
    else    modify(rson(x), p, d);
    t[x].v = std::min(t[lson(x)].v, t[rson(x)].v);
}

int query(int x, int l, int r, int k) {
    if (t[x].v >= k)    return -1;
    if (t[x].l == t[x].r)    return t[x].id;
    int mid = (t[x].l + t[x].r) >> 1;
    if (r <= mid)    return query(lson(x), l, r, k);
    else if (l > mid)    return query(rson(x), l, r, k);
    else {
        int s1 = query(lson(x), l, r, k);
        if (s1 != -1)    return s1;
        else    return query(rson(x), l, r, k);
    }
}

int main() {
    read(n), read(m1), read(m2);
    for (int i = 1; i <= m1; ++i)    read(a[i].l), read(a[i].r), A1[i * 2 - 1] = a[i].l, A1[i * 2] = a[i].r;
    for (int i = 1; i <= m2; ++i)    read(b[i].l), read(b[i].r), A2[i * 2 - 1] = b[i].l, A2[i * 2] = b[i].r;
    std::sort(A1 + 1, A1 + m1 + m1 + 1), std::sort(A2 + 1, A2 + m2 + m2 + 1);
    for (int i = 1; i <= m1; ++i)    a[i].l = std::lower_bound(A1 + 1, A1 + m1 + m1 + 1, a[i].l) - A1, a[i].r = std::lower_bound(A1 + 1, A1 + m1 + m1 + 1, a[i].r) - A1;
    for (int i = 1; i <= m2; ++i)    b[i].l = std::lower_bound(A2 + 1, A2 + m2 + m2 + 1, b[i].l) - A2, b[i].r = std::lower_bound(A2 + 1, A2 + m2 + m2 + 1, b[i].r) - A2;
    std::sort(a + 1, a + m1 + 1), std::sort(b + 1, b + m2 + 1);
    buildTree(1, 1, m1);
    for (int i = 1; i <= m1; ++i) {
        int pos = query(1, 1, cnt, a[i].l);
        if (pos == -1) {
            ++cnt;
            modify(1, cnt, a[i].r);
            ++f1[cnt];
        } else {
            ++f1[pos];
            modify(1, pos, a[i].r);
        }
    }
    for (int i = 1; i <= 800000; ++i)    t[i].l = t[i].r = t[i].v = t[i].id = 0;
    buildTree(1, 1, m2);
    cnt = 0;
    for (int i = 1; i <= m2; ++i) {
        int pos = query(1, 1, cnt, b[i].l);
        if (pos == -1) {
            ++cnt;
            modify(1, cnt, b[i].r);
            ++f2[cnt];
        } else {
            ++f2[pos];
            modify(1, pos, b[i].r);
        }
    }
    for (int i = 1; i <= n; ++i)    f1[i] += f1[i - 1], f2[i] += f2[i - 1];
    for (int i = 0; i <= n; ++i)    ans = std::max(ans, f1[i] + f2[n - i]);
    printf("%d\n", ans);
    return 0;
}
Last modification:October 24th, 2021 at 06:32 pm