Submission #1160133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160133		Hanksburger	Advertisement 2 (JOI23_ho_t2)	C++20	59 / 100	2095 ms	1114112 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll, ll> > vec;
vector<int> seg, iL, iR, jL, jR;
ll a, b, num=1000000000;
void create()
{
    seg.push_back(0);
    iL.push_back(0);
    iR.push_back(0);
    jL.push_back(0);
    jR.push_back(0);
}
void upd2(int i, ll l, ll r)
{
    //cout << "upd2 " << i << ' ' << l << ' ' << r << '\n';
    if (l==r)
    {
        seg[i]++;
        return;
    }
    ll mid=(l+r)/2;
    if (b<=mid)
    {
        if (!jL[i])
        {
            jL[i]=seg.size();
            create();
        }
        upd2(jL[i], l, mid);
    }
    else
    {
        if (!jR[i])
        {
            jR[i]=seg.size();
            create();
        }
        upd2(jR[i], mid+1, r);
    }
    seg[i]=seg[jL[i]]+seg[jR[i]];
}
void upd1(int i, ll l, ll r)
{
    //cout << "upd1 " << i << ' ' << l << ' ' << r << '\n';
    upd2(i, 1, num*2);
    if (l==r)
        return;
        ll mid=(l+r)/2;
    if (a<=mid)
    {
        if (!iL[i])
        {
            iL[i]=seg.size();
            create();
        }
        upd1(iL[i], l, mid);
    }
    else
    {
        if (!iR[i])
        {
            iR[i]=seg.size();
            create();
        }
        upd1(iR[i], mid+1, r);
    }
}
int qry2(int i, ll l, ll r)
{
    //cout << "qry2 " << i << ' ' << l << ' ' << r << '\n';
    if (r<=b)
        return seg[i];
    ll mid=(l+r)/2, res=jL[i]?qry2(jL[i], l, mid):0;
    if (res)
        return res;
    if (mid<b)
        res+=jR[i]?qry2(jR[i], mid+1, r):0;
    return res;
}
int qry1(int i, ll l, ll r)
{
    //cout << "qry1 " << i << ' ' << l << ' ' << r << '\n';
    if (r<=a)
        return qry2(i, 1, num*2);
    ll mid=(l+r)/2, res=iL[i]?qry1(iL[i], l, mid):0;
    if (res)
        return res;
    if (mid<a)
        res+=iR[i]?qry1(iR[i], mid+1, r):0;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    create();
    create();
    int n, cnt=0;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        ll x, y;
        cin >> x >> y;
        vec.push_back({y, x});
    }
    sort(vec.begin(), vec.end(), greater<pair<int, int> >());
    for (int i=0; i<n; i++)
    {
        ll y=vec[i].first, x=vec[i].second;
        a=-x-y+num*2+1, b=x-y+num;
        if (!qry1(1, 1, num*2))
        {
            upd1(1, 1, num*2);
            cnt++;
        }
    }
    cout << cnt;
}

• Subtask 1: 0 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31