oj.uz

Submission #1093408

# Submission time Handle Problem Language Result Execution time Memory
1093408 2024-09-26T18:49:06 Z ibm2006 None (JOI16_matryoshka) C++17
11 / 100
 1 ms 348 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -