oj.uz

Submission #374768

# Submission time Handle Problem Language Result Execution time Memory
374768 2021-03-08T06:39:29 Z daniel920712 Exhibition (JOI19_ho_t2) C++14
0 / 100
 71 ms 141292 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

using namespace std;

struct A
{
    long long l,r;
    long long nxl,nxr;
    pair < long long , long long > big;
}Node[3000005];
pair < long long , long long > all[100005];
long long sz[100005],now=1;
void New(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].big=make_pair(0,0);
}
pair < long long , long long > Find(long long l,long long r,long long here)
{
    //printf("%lld %lld %lld\n",l,r,here);
    if(here==-1) return make_pair(0,0);
    if(l==Node[here].l&&r==Node[here].r) return Node[here].big;
    if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
    else return max(Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
void cha(long long where,pair < long long , long long > con,long long here)
{
    //printf("aa %lld %lld\n",where,here);
    Node[here].big=max(Node[here].big,con);
    if(Node[here].l==where&&Node[here].r==where) return;
    if(where<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
        }
        cha(where,con,Node[here].nxl);
    }
    else
    {
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr);
        }
        cha(where,con,Node[here].nxr);
    }
}
int main()
{
    long long N,M,ans=0,t,i,a,b;
    pair < long long , long long > tt;
    scanf("%lld %lld",&N,&M);
    New(0,1000000000,0);
    for(i=0;i<N;i++) scanf("%lld %lld",&all[i].first,&all[i].second);
    sort(all,all+N);
    for(i=0;i<M;i++) scanf("%lld",&sz[i]);
    sort(sz,sz+M);
    /*for(i=0;i<M;i++) printf("%lld ",sz[i]);
    printf("\n");*/
    for(i=0;i<N;i++)
    {
        tt=Find(0,all[i].second,0);
        a=tt.first;
        b=0-tt.second;
        t=(long long) (lower_bound(sz+b,sz+M,all[i].first)-sz);
        if(t!=M)
        {
            ans=max(ans,a+1);
            cha(all[i].second,make_pair(a+1,0-t-1),0);
        }

        //printf("%lld %lld %lld %lld\n",all[i].first,all[i].second,(long long) M-(lower_bound(sz,sz+M,all[i].first)-sz),Find(0,all[i].second,0)+1);


    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:67:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     for(i=0;i<N;i++) scanf("%lld %lld",&all[i].first,&all[i].second);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     for(i=0;i<M;i++) scanf("%lld",&sz[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141292 KB Output is correct
2 Correct 71 ms 141292 KB Output is correct
3 Correct 65 ms 141292 KB Output is correct
4 Correct 63 ms 141292 KB Output is correct
5 Incorrect 64 ms 141292 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141292 KB Output is correct
2 Correct 71 ms 141292 KB Output is correct
3 Correct 65 ms 141292 KB Output is correct
4 Correct 63 ms 141292 KB Output is correct
5 Incorrect 64 ms 141292 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141292 KB Output is correct
2 Correct 71 ms 141292 KB Output is correct
3 Correct 65 ms 141292 KB Output is correct
4 Correct 63 ms 141292 KB Output is correct
5 Incorrect 64 ms 141292 KB Output isn't correct
6 Halted 0 ms 0 KB -