Submission #74718

#	Time	Username	Problem	Language	Result	Execution time	Memory
74718		OmarHashim	trapezoid (balkan11_trapezoid)	C++14	0 / 100	202 ms	46868 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;

#define scl(x) scanf("%lld",&x)
#define sc(x)  scanf("%d",&x)
#define ll long long
#define lop(i,n) for(int i=0;i<n;++i)
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const int N=1e5+100,LG=24;
int tree[N*LG],L[N*LG],R[N*LG],ne;
int dp[N];
void build(int root,int s,int e){
	if(s==e)return;
	L[root]=ne++;
	R[root]=ne++;
	int m=s+((e-s)>>1);
	build(L[root],s,m);
	build(R[root],m+1,e);
}
void upd(int nroot,int root,int s,int e,int i,int val){
	if(s==e){
		tree[nroot]=max(val,tree[root]);
		return;
	}
	int m=s+((e-s)>>1);
	if(i<=m){
		L[nroot]=ne++;
		R[nroot]=R[root];
		upd(L[nroot],L[root],s,m,i,val);
	}
	else {
		L[nroot]=L[root];
		R[nroot]=ne++;
		upd(R[nroot],R[root],m+1,e,i,val);
	}
	tree[nroot]=max(tree[L[nroot]],tree[R[nroot]]);
}
int get(int root,int s,int e,int l,int r){
	if(e<l||s>r)return 0;
	if(s>=l&&e<=r)return tree[root];
	int m=s+((e-s)>>1);
	return max(get(L[root],s,m,l,r),get(R[root],m+1,e,l,r));
}


struct node{
	int a,b,c,d;
	bool operator<(const node &o)const{
		return a<o.a;
	}
}arr[N];
int n;
vector<int> uncom;
int roots[N];

int main(){
#ifndef ONLINE_JUDGE
	//freopen("i.txt","r",stdin);
#endif
	sc(n);
	lop(i,n){
		sc(arr[i].a),sc(arr[i].b);
		sc(arr[i].c),sc(arr[i].d);
		uncom.push_back(arr[i].c);
	}
	uncom.push_back(1e9+1);
	sort(uncom.begin(),uncom.end());
	uncom.erase(unique(uncom.begin(),uncom.end()),uncom.end());
	lop(i,n){
		arr[i].c=lower_bound(uncom.begin(),uncom.end(),arr[i].c)-uncom.begin();
		arr[i].d=upper_bound(uncom.begin(),uncom.end(),arr[i].d)-uncom.begin();
	}
	sort(arr,arr+n);
	arr[n].a=1e9+1;
	roots[n]=ne++;
	build(roots[n],0,uncom.size()-1);
	for(int i=n-1;i>=0;i--){
		node qr;
		qr.a=arr[i].b;
		int start=upper_bound(arr+i+1,arr+n+1,qr)-arr;
		dp[i]=1+get(roots[start],0,uncom.size()-1,arr[i].d,uncom.size()-1);
		roots[i]=ne++;
		upd(roots[i],roots[i+1],0,uncom.size()-1,arr[i].c,dp[i]);
	}
	printf("%d\n",dp[0]);
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sc(x)  scanf("%d",&x)
                ~~~~~^~~~~~~~~
trapezoid.cpp:62:2: note: in expansion of macro 'sc'
  sc(n);
  ^~
trapezoid.cpp:64:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sc(arr[i].a),sc(arr[i].b);
               ^
trapezoid.cpp:64:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
trapezoid.cpp:65:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sc(arr[i].c),sc(arr[i].d);
               ^
trapezoid.cpp:65:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 0 / 100