Submission #1205755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205755		vnedu	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	110 ms	7236 KiB

matryoshka

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

const int N = 2e5 + 10;
const int Q = 2e5 + 10;
int n,_q,ans[Q];
pair<int,int> a[N];
deque<int> dq;
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 a>S.a;
    }
} q[Q];
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<=_q;++i) q[i].input(),q[i].id=i;
    sort(q+1,q+1+_q);
    int ptr=n+1;
    for(int i=1;i<=_q;++i)
    {
        while(ptr>1 && a[ptr-1].first>=q[i].a)
        {
            int pos=lower_bound(dq.begin(),dq.end(),a[ptr-1].second+1)-dq.begin();
            if(pos==(int)dq.size()) dq.push_back(a[ptr-1].second);
            else dq[pos]=a[ptr-1].second;
            --ptr;
        }
        ans[q[i].id]=lower_bound(dq.begin(),dq.end(),q[i].b+1)-dq.begin();
    }
    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