oj.uz

Submission #202025

# Submission time Handle Problem Language Result Execution time Memory
202025 2020-02-13T05:37:37 Z gs18115 허수아비 (JOI14_scarecrows) C++14
0 / 100
 490 ms 63728 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19192 KB Output is correct
2 Incorrect 17 ms 19192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 20088 KB Output is correct
2 Incorrect 23 ms 19576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 63728 KB Output is correct
2 Incorrect 490 ms 35952 KB Output isn't correct
3 Halted 0 ms 0 KB -