Submission #1138510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138510		abcdxyz123	허수아비 (JOI14_scarecrows)	C++17	100 / 100	1454 ms	70120 KiB

scarecrows

#include<bits/stdc++.h>
#define push_back emplace_back
#define ll long long
#define maxn 300005
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
int n;
pi p[maxn];
int numX;
int valX[maxn];
int numY;
int valY[maxn];
vector<int>dx[maxn];
struct
{
    int s[maxn];
    void update(int x,int val)
    {
        for(;x<=numY+1;x+=x&(-x))
        {
            s[x]+=val;
        }
    }
    int get(int x)
    {
        int sum=0;
        for(;x>0;x-=x&(-x))
        {
            sum+=s[x];
        }
        return sum;
    }
    int get(int l,int r)
    {
        return get(r)-get(l-1);
    }
}bit;
int cnt[maxn];
int l[maxn];
int r[maxn];
vector<int>sk[3][maxn];
ll ans=0;
void solve(int lo,int hi)
{
    if(lo==hi)
    {
        ans+=max((int)dx[lo].size()-1,0);
        return ;
    }
    int mid=(lo+hi)/2;

    solve(lo,mid);
    solve(mid+1,hi);

    multiset<int>val;
    val.insert(0);
    val.insert(numY+1);
    vector<int>pos;

    for(int i=mid;i>=lo;i--)
    {
        for(int j:dx[i])
        {
            int y=p[j].se;
            cnt[y]++;
            if(cnt[y]==1)val.insert(y);
        }
        for(int j:dx[i])
        {
            int y=p[j].se;
            if(cnt[y]==1)
            {
                auto it=val.lower_bound(y);
                auto it1=it;
                int pre=*(--it);
                int nxt=*(++it1);

                l[j]=pre+1;
                r[j]=nxt-1;

                sk[0][pre+1].push_back(j);
                sk[1][nxt].push_back(j);
                pos.push_back(pre+1);
                pos.push_back(nxt);
            }
            else
            {
                l[j]=r[j]=0;
            }
        }
    }
    for(int i=mid;i>=lo;i--)
    {
        for(int j:dx[i])
        {
            int y=p[j].se;
            cnt[y]--;
        }
    }

    val.clear();
    val.insert(0);
    val.insert(numY+1);
    for(int i=mid+1;i<=hi;i++)
    {
        for(int j:dx[i])
        {
            int y=p[j].se;
            cnt[y]++;
            if(cnt[y]==1)val.insert(y);
        }
        for(int j:dx[i])
        {
            int y=p[j].se;
            if(cnt[y]==1)
            {
                auto it=val.lower_bound(y);
                auto it1=it;
                int pre=*(--it);
                int nxt=*(++it1);

                l[j]=pre+1;
                r[j]=min(y,nxt-1);

                sk[2][y].push_back(j);
                pos.push_back(y);
            }
            else
            {
                l[j]=r[j]=0;
            }
        }
    }
    for(int i=mid+1;i<=hi;i++)
    {
        for(int j:dx[i])
        {
            int y=p[j].se;
            cnt[y]--;
        }
    }

    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    for(int i:pos)
    {
        for(int j:sk[0][i])
        {
            bit.update(p[j].se,1);
        }
        for(int j:sk[1][i])
        {
            bit.update(p[j].se,-1);
        }
        for(int j:sk[2][i])
        {
            ans+=bit.get(l[j],r[j]);
        }
    }
    for(int i:pos)
    {
        sk[0][i].clear();
        sk[1][i].clear();
        sk[2][i].clear();
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        p[i]={x,y};
        valX[++numX]=x;
        valY[++numY]=y;
    }
    sort(valX+1,valX+numX+1);
    numX=unique(valX+1,valX+numX+1)-valX-1;
    sort(valY+1,valY+numY+1);
    numY=unique(valY+1,valY+numY+1)-valY-1;
    for(int i=1;i<=n;i++)
    {
        p[i].fi=lower_bound(valX+1,valX+numX+1,p[i].fi)-valX;
        p[i].se=lower_bound(valY+1,valY+numY+1,p[i].se)-valY;
        dx[p[i].fi].push_back(i);
    }
    solve(1,numX);
    cout<<ans;
}

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