Submission #1225677

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int n, q;
const int N = 300000;
int a[N], b[N], c[N];
int del[N], odel[N], ncg[N], acg[N];
struct node
{
    int l, r;
} interval[N];
int tot;
int used[N], ipb, npb;
int comp_1(node a, node b) {return a.r > b.r;}
struct Scomp_1 { int operator () (node a, node b) {return a.l < b.l;}};
int comp_2(node a, node b) {return a.l < b.l;}
struct Scomp_2 { int operator () (node a, node b) {return a.r > b.r;}};
int ans0 = 0, ans[N];
multiset <node, Scomp_1> S1;
multiset <node, Scomp_2> S2;
int main()
{
    cin >> n; n ++;
    for (int i = 1; i < n; ++ i)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= n; ++ i)
        cin >> c[i];
    sort(c + 1, c + n + 1);
    for (int i = 1; i < n; ++ i)
    {
        a[i] = lower_bound(c + 1, c + n + 1, a[i]) - c,
        b[i] = lower_bound(c + 1, c + n + 1, b[i]) - c;
        if (b[i] < a[i]) interval[++ tot] = (node){b[i], a[i] - 1};
    }
    for (int i = 1; i <= n; ++ i)
        del[i] = -1;
    for (int i = 1; i < n; ++ i)
        del[a[i]] ++;
    for (int i = 1; i <= n; ++ i)
        del[i] += del[i - 1];
    for (int i = 1; i <= n; ++ i)
        odel[i] = del[i];

    sort(interval + 1, interval + tot + 1, comp_1);
    for (int i = n, j = 1, p = 0; i >= 1; -- i)
    {
        p += ncg[i];
        del[i] += p;
        while (j <= tot && interval[j].r == i)
        {
            S1.insert(interval[j]); j ++;
        }
        while (del[i] < -1)
        {
            multiset <node, Scomp_1> :: iterator nw;
            if (S1.empty())
                goto LETS_SAY_GG;
            nw = S1.begin();
            if (i < nw -> l)
                goto LETS_SAY_GG;
            else
            {
                ans0 --;
                acg[(nw -> l)] ++;
                acg[(nw -> r) + 1] --;
                ncg[(nw -> l) - 1] --;
                p ++;
                del[i] ++;
            }
            S1.erase(nw);
        }
    }

    for (int i = 1; i <= n; ++ i)
        acg[i] += acg[i - 1], del[i] = odel[i] + acg[i];

    tot = 0;
    for (multiset <node, Scomp_1> :: iterator it = S1.begin(); it != S1.end(); ++ it)
        interval[++ tot] = *it;

    sort(interval + 1, interval + tot + 1, comp_2);
    memset(ncg, 0, sizeof ncg);
    for (int i = 1, j = 1, p = 0; i <= n; ++ i)
    {
        if (npb)
        {
            ans[i] = 666;
            continue;
        }
        p += ncg[i];
        del[i] += p;
        while (j <= tot && interval[j].l == i)
        {
            S2.insert(interval[j]); j ++;
        }
        if (del[i] < 0)
        {
            multiset <node, Scomp_2> :: iterator nw;
            if (S2.empty()) goto I_WANT_JUMP;
            nw = S2.begin();
            if (i > nw -> r)
            {
                I_WANT_JUMP:npb = 1;
                ans[i] = 666;
                continue;
            }
            else
            {
                ans[i] = ans[i - 1] - 1;
                ncg[(nw -> r) + 1] --;
                p ++;
                del[i] ++;
            }
            S2.erase(nw);
        }
        else
            ans[i] = ans[i - 1];
    }

    cin >> q;
    for (int i = 1; i <= q; ++ i)
    {
        int d, e;
        cin >> d >> e;
        d = lower_bound(c + 1, c + n + 1, d) - c,
        e = lower_bound(c + 1, c + n + 1, e) - c;
        int nwans = -1;
        if (ans[d - 1] != 666) nwans = max(nwans, n + ans[d - 1] + ans0);
        if (ans[e - 1] != 666) nwans = max(nwans, n - 1 + ans[e - 1] + ans0);
        cout << nwans << "\n";
    }
    return 0;
    LETS_SAY_GG:cin >> q;
    for (int i = 1; i <= q; ++ i)
    {
        cout << -1 << "\n";
    }
}

Submission Info

Judge Result