Submission #1093408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093408		ibm2006	Matryoshka (JOI16_matryoshka)	C++17	11 / 100	1 ms	348 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll siz=1048576;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],seg[2200000],ans[1100000],q;
pair<pair<ll,ll>,pair<ll,ll>> p[1100000];
vector<ll> u,v;
void f(ll x)
{
    seg[x]=max(seg[x*2],seg[x*2+1]);
    if(x==1)
        return;
    f(x/2);
}
ll g(ll x,ll y,ll z)
{
    if(l>y||x>r)
        return 0;
    if(l<=x&&y<=r)
        return seg[z];
    return max(g(x,(x+y)/2,z*2),g((x+y)/2+1,y,z*2+1));
}
int main()
{
    scanf("%lld %lld",&n,&q);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld",&x,&y);
        p[i]={{y,0},{-x,i}};
        u.push_back(x);
        u.push_back(y);
    }
    for(i=1;i<=q;i++)
    {
        scanf("%lld %lld",&x,&y);
        p[i+n]={{y,1},{-x,i}};
        u.push_back(x);
        u.push_back(y);
    }
    sort(u.begin(),u.end());
    for(i=1;i<=n+q;i++)
    {
        p[i].second.first*=-1;
        p[i].first.first=lower_bound(u.begin(),u.end(),p[i].first.first)-u.begin()+1;
        p[i].second.first=lower_bound(u.begin(),u.end(),p[i].second.first)-u.begin()+1;
    }
    sort(p+1,p+n+q+1);
    /*for(i=1;i<=n;i++)
    {
        swap(p[i].first,p[i].second);
    }*/
    v.clear();
    for(i=1;i<=n+q;i++)
    {
        x=p[i].second.first;
        y=p[i].first.first;
        z=p[i].second.second;
        t=p[i].first.second;
        //printf("(%lld,%lld,%lld,%lld)\n",x,y,z,t);
        if(t==0)
        {
            l=x;
            r=siz;
            b[i]=g(1,siz,1)+1;
            seg[x+siz-1]=max(seg[x+siz-1],b[i]);
           // printf("(%lld)\n",b[i]);
        f((x+siz-1)/2);
        continue;
        }
        l=x;
        r=siz;
        ans[z]=g(1,siz,1);
    }
    for(i=1;i<=q;i++)
        printf("%lld\n",ans[i]);
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%lld %lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
matryoshka.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
matryoshka.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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