Submission #706327

#	Time	Username	Problem	Language	Result	Execution time	Memory
706327		blacktulip	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	340 KiB

joi2019_ho_t2

// I am teacher of MakaPakka
// LOUGI_ID:643723
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

using namespace std;

inline int in(){
    int x;
    scanf("%d",&x);
    return x;
}

#define fi first
#define se second
#define mid ((start+end)/2)
#define pb push_back
#define FOR for(int i=1;i<=n;i++)
#define ort ((bas+son)/2)

const long long inf = 100000000000000;
const int li = 100005;
const int mod = 1000000007;

int n,m,a[li],k,t,cev,b[li],c[li],d[li],tree1[li*4];
vector<int> v;
char s[li];
pair<int,int> p[li],tree[li*4];

inline void update(int node,int start,int end,int l,int r,pair<int,int> val){
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){tree[node]=max(tree[node],val);return ;}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline pair<int,int> query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return {0,0};
	if(start>=l && end<=r)return tree[node];
	return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

inline void build(int node,int start,int end){
	if(start==end){tree1[node]=d[start];return ;}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree1[node]=max(tree1[node*2],tree1[node*2+1]);
}

inline int query1(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return tree1[node];
	return max(query1(node*2,start,mid,l,r),query1(node*2+1,mid+1,end,l,r)); 
}

int main(void){
    n=in(),m=in();
    FOR{
		a[i]=in(),b[i]=in();
		c[i]=b[i];
	}
	sort(c+1,c+n+1);
	FOR{
		int bas=1;
		int son=n;
		while(bas<=son){
			if(b[i]<=c[ort])son=ort-1;
			else bas=ort+1;
		}
		b[i]=bas;
		p[i]={a[i],b[i]};
		//~ cout<<i<<" :: "<<b[i]<<endl;
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=m;i++){
		d[i]=in();
	}
	build(1,1,m);
	for(int i=1;i<=n;i++){
		//~ while(yes>0 && d[yes]>=p[i].fi)yes--;
		//~ int kal=m-yes;
		pair<int,int> tut=query(1,1,n,p[i].se,n);
		int at=tut.fi;
		int kat=tut.se;
		int bas=kat+1;
		int son=m;
		while(bas<=son){
			if(query1(1,1,m,kat+1,ort)>=p[i].fi)son=ort-1;
			else bas=ort+1;
		}
		
		if(bas<=m)update(1,1,n,p[i].se,p[i].se,{at+1,bas});
	}
	printf("%d\n",query(1,1,n,1,n).fi);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int in()':
joi2019_ho_t2.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50