Submission #202025

#	Time	Username	Problem	Language	Result	Execution time	Memory
202025		gs18115	허수아비 (JOI14_scarecrows)	C++14	0 / 100	490 ms	63728 KiB

scarecrows

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct seg
{
    vector<pi>t[800010];
    vector<int>qv;
    void si(int n,int s,int e,pi p)
    {
        while(!t[n].empty()&&t[n].back().se<p.se)
            t[n].pop_back();
        t[n].eb(p);
        if(s==e)
            return;
        int m=(s+e)/2;
        if(p.se>m)
            si(n*2+1,m+1,e,p);
        else
            si(n*2,s,m,p);
        return;
    }
    void sq(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
        {
            qv.eb(n);
            return;
        }
        int m=(s+e)/2;
        sq(n*2,s,m,S,E);
        sq(n*2+1,m+1,e,S,E);
        return;
    }
    void si(int n,pi p)
    {
        si(1,0,n-1,p);
        return;
    }
    int sq(int n,pi p)
    {
        qv.clear();
        sq(1,0,n-1,0,p.se);
        int ans=0;
        for(int&x:qv)
            if(!t[x].empty())
                ans+=lower_bound(all(t[x]),p)-t[x].begin(),p=min(p,t[x][0]);
        return ans;
    }
}st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pi>v(n);
    vector<int>y;
    for(pi&t:v)
        cin>>t.fi>>t.se,y.eb(t.se);
    sort(all(y));
    sort(all(v));
    ll ans=0;
    for(pi&t:v)
    {
        t.se=lower_bound(all(y),t.se)-y.begin();
        ans+=st.sq(n,t);
        st.si(n,t);
    }
    cout<<ans<<endl;
    return 0;
}

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