Submission #1264551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264551		nqknht	허수아비 (JOI14_scarecrows)	C++20	15 / 100	4094 ms	39424 KiB

scarecrows

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()
#define LS(x) (1 << x)

const ll I = 2e5 + 9;
const ll Z = 1e9 + 7;

using namespace std;

ll rs = 0;
int n, nex[I], prv[I];
pair<int, int> b[I];
set<int> s;
vector<int> S[I * 2];

struct mix
{
    int x, y;
} a[I];

void preST(int x, int l, int r)
{
    if (l == r)
    {
        S[x].assign(1, 0);
        return;
    }
    S[x].assign(r - l + 1, 0);
    int mid = (l + r) / 2;
    preST(x * 2, l, mid);
    preST(x * 2 + 1, mid + 1, r);
}

void build(int x, int l, int r)
{
    if (l == r)
    {
        S[x][0] = b[l].se;
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    int id = 0, i1 = 0, i2 = 0;
    while (id != r - l + 1)
    {
        if (i1 == mid - l + 1)
        {
            S[x][id] = S[x * 2 + 1][i2];
            i2++;
            id++;
        }
        else if (i2 == r - mid)
        {
            S[x][id] = S[x * 2][i1];
            i1++;
            id++;
        }
        else if (S[x * 2][i1] < S[x * 2 + 1][i2])
        {
            S[x][id] = S[x * 2][i1];
            i1++;
            id++;
        }
        else
        {
            S[x][id] = S[x * 2 + 1][i2];
            id++;
            i2++;
        }
    }
}

int get(int x, int l, int r, int L, int R, int val)
{
    if (r < L || R < l || r < l || R < L)
        return 0;
    if (L <= l && r <= R)
    {
        auto id = upper_bound(S[x].begin(), S[x].begin() + (r - l + 1), val) - S[x].begin();
        return id;
    }
    int mid = (l + r) / 2;
    return get(x * 2, l, mid, L, R, val) + get(x * 2 + 1, mid + 1, r, L, R, val);
}

void dc(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    s.clear();
    for (int i = mid; i >= l; i--)
    {
        if (s.empty())
        {
            nex[i] = 2000000000;
            s.insert(a[i].y);
        }
        else
        {
            auto id = lower_bound(s.begin(), s.end(), a[i].y);
            if (id == s.end())
                nex[i] = 2000000000;
            else
                nex[i] = *id;
            s.insert(a[i].y);
        }
    }
    s.clear();
    for (int i = mid + 1; i <= r; i++)
    {
        if (s.empty())
        {
            prv[i] = -2000000000;
            s.insert(a[i].y);
        }
        else
        {
            auto id = upper_bound(s.begin(), s.end(), a[i].y);
            if (id == s.begin())
                prv[i] = -2000000000;
            else
                prv[i] = *prev(id);
            s.insert(a[i].y);
        }
        b[i - mid] = {a[i].y, prv[i]};
    }
    int Nr = r - mid;
    sort(b + 1, b + Nr + 1);
    build(1, 1, Nr);
    // cout << l << " " << r << " || " << rs << " ";
    // cout << prv[4] << "\n";
    // for(int i = 0; i < 2; i ++)
    // cout << S[1][i] << " ";
    // cout << "\n";
    // cout << S[3][0] << "\n";
    // cout << get(1, 1, 2, 1, 2, 1) << "\n";
    for (int i = l; i <= mid; i++)
    {
        int l_ = 1, r_ = r - mid, savL = -1, savR = -1, tg;
        while (l_ <= r_)
        {
            tg = (l_ + r_) / 2;
            if (b[tg].fi >= a[i].y)
            {
                savL = tg;
                r_ = tg - 1;
            }
            else
                l_ = tg + 1;
        }
        l_ = 1, r_ = r - mid;
        while (l_ <= r_)
        {
            tg = (l_ + r_) / 2;
            if (b[tg].fi <= nex[i])
            {
                savR = tg;
                l_ = tg + 1;
            }
            else
                r_ = tg - 1;
        }
        if (savL != -1 && savR != -1)
        {
            rs += get(1, 1, Nr, savL, savR, a[i].y);
            // cout << i << " " << get(1, 1, Nr, savL, savR, a[i].y) << "\n";
            // cout << i << " " << savL << " " << savR << " " << a[i].y << "\n";
        }
    }
    // cout << rs << "\n";
    dc(l, mid);
    dc(mid + 1, r);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, [&](mix A, mix B)
         { return A.x < B.x; });
    preST(1, 1, n);
    dc(1, n);
    cout << rs;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 85