MENU

梦境

20181106A.pdf

贪心,对梦境和转折点都排序,对于每个转折点找到包含它的且右端点最小的区间,与其配对。用堆维护一下。

#include<cstdio>
#include<utility>
#include<queue>
#include<algorithm>
#include<vector>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("O2")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
using namespace std;
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { *oS++ = '0'; return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("dream.in", "r", stdin), freopen("dream.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), t[200001], ans;
pair<int, int>dream[200001];
struct cmp { bool operator()(pair<int, int>a, pair<int, int>b) { return a.second > b.second; } };
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp>pq;
int main() {
    for (int i = 1; i <= n; ++i)dream[i].first = ip.rd<int>(), dream[i].second = ip.rd<int>();
    sort(dream + 1, dream + n + 1);
    for (int i = 1; i <= m; ++i)t[i] = ip.rd<int>();
    sort(t + 1, t + m + 1);
    for (int i = 1, j = 1; i <= m; ++i) {
        while (j <= n && dream[j].first <= t[i])pq.push(dream[j++]);
        while (pq.size() && pq.top().second < t[i])pq.pop();
        if (pq.size())++ans, pq.pop();
    }
    ip.print(ans);
}
Leave a Comment

captcha
请输入验证码