Submission #1205637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205637		vnedu	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	137 ms	8772 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int Q = 2e5 + 10;
int n,_q,bit[N],ans[Q];
pair<int,int> a[N],p[N];
bool cmp(pair<int,int> &x, pair<int,int> &y)
{
    if(x.first!=y.first) return x.first<y.first;
    return x.second>y.second;
}
struct Query
{
    int a,b,id;
    Query() {}
    void input()
    {
        cin>>a>>b;
    }
    bool operator < (const Query &S) const
    {
        return b<S.b;
    }
} q[Q];
void update(int x, int val)
{
    x=n-x+1;
    while(x<=n)
    {
        bit[x]=max(bit[x],val);
        x+=x&-x;
    }
}
int get(int x)
{
    x=n-x+1;
    int ans=0;
    while(x>=1)
    {
        ans=max(ans,bit[x]);
        x-=x&-x;
    }
    return ans;
}
void solve()
{
    cin>>n>>_q;
    for(int i=1;i<=n;++i) cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i) p[i]={a[i].second,i};
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=_q;++i) q[i].input(),q[i].id=i;
    sort(q+1,q+1+_q);
    int ptr=0;
    for(int i=1;i<=_q;++i)
    {
        while(ptr<n && p[ptr+1].first<=q[i].b)
        {
            int val=get(p[ptr+1].second)+1;
            update(p[ptr+1].second,val);
            ++ptr;
//            cout<<ptr<<' '<<val<<' '<<p[ptr].second<<'\n';
        }
        int pos=lower_bound(a+1,a+1+n,make_pair(q[i].a,INT_MIN))-a;
//        cout<<pos<<'\n';
        ans[q[i].id]=get(pos);
//        cout<<q[i].id<<' '<<get(pos)<<'\n';
    }
//    cout<<"DS\n";
//    for(int i=1;i<=n;++i) cout<<bit[i]<<' ';
//    cout<<'\n';
//    cout<<get(2)<<'\n';
    for(int i=1;i<=_q;++i) cout<<ans[i]<<'\n';
}
int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int testcase=1;
//    cin>>testcase;
    while(testcase--)
        solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49