제출 #1252401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252401		tvgk	허수아비 (JOI14_scarecrows)	C++20	100 / 100	1006 ms	259660 KiB

scarecrows

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

int n, mn;
ii h[mxN], a[mxN];
set<ii> s[mxN * 4];
vector<int> bit[mxN * 4];

ii rev(ii a)
{
    return {a.se, a.fi};
}

void Build(int j = 1, int l = 1, int r = n)
{
    bit[j].resize(r - l + 2);
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
}

int Get_bit(int j)
{
    int i = (*s[j].upper_bound(ii(mn, 0))).se + 1;
    int res = 0;
    while (i < bit[j].size())
    {
        res += bit[j][i];
        i += i & -i;
    }
    mn = min(mn, (*s[j].begin()).fi);
    return res;
}

void Upd_Bit(int id, int j, int val)
{
    while (j > 0)
    {
        bit[id][j] += val;
        j -= j & (-j);
    }
}

int Get(int vt, int j = 1, int l = 1, int r = n)
{
    if (r <= vt || s[j].empty())
        return 0;

    if (vt < l)
        return Get_bit(j);

    int mid = (l + r) / 2;
    return Get(vt, j * 2, l, mid) + Get(vt, j * 2 + 1, mid + 1, r);
}

void Upd(int vt, int j = 1, int l = 1, int r = n)
{
    if (l > vt || vt > r)
        return;

    while (s[j].size() && (*s[j].begin()).se > vt - l + 1)
    {
        Upd_Bit(j, (*s[j].begin()).se, -1);
        s[j].erase(s[j].begin());
    }
    Upd_Bit(j, vt - l + 1, 1);
    s[j].insert({h[vt].se, vt - l + 1});

    if (l == r)
        return;

    int mid = (l + r) / 2;
    Upd(vt, j * 2, l, mid);
    Upd(vt, j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        h[i] = {a[i].se, a[i].fi};
    }
    sort(h + 1, h + n + 1);
    sort(a + 1, a + n + 1, greater<ii>());

    Build();
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int tmp = lower_bound(h + 1, h + n + 1, rev(a[i])) - h;
        mn = inf;
        ans += Get(tmp);
        Upd(tmp);
    }
    cout << ans;
}

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