oj.uz

Submission #706273

# Submission time Handle Problem Language Result Execution time Memory
706273 2023-03-06T08:35:37 Z blacktulip Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 212 KB 
// 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],tree[li*4];
vector<int> v;
char s[li];
pair<int,int> p[li];

inline void update(int node,int start,int end,int l,int r,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 int query(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 tree[node];
	return max(query(node*2,start,mid,l,r),query(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]};
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=m;i++){
		d[i]=in();
	}
	sort(d+1,d+m+1);
	int yes=m;
	for(int i=n;i>=1;i--){
		while(yes>0 && d[yes]>=p[i].fi)yes--;
		int kal=m-yes;
		int at=query(1,1,n,1,p[i].se);
		update(1,1,n,p[i].se,p[i].se,min(at+1,kal));
	}
	printf("%d\n",query(1,1,n,1,n));
    return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -