Submission #198826

#	Time	Username	Problem	Language	Result	Execution time	Memory
198826		mahmoudbadawy	trapezoid (balkan11_trapezoid)	C++17	100 / 100	237 ms	8172 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5,MOD=30013;

struct trap{
	int l1,r1,l2,r2;
} arr[N];

vector<int> cmp;
int btree[2*N*4],stree[2*N*4],dp[N],dpways[N];
int sortl[N],sortr[N];
int n;

bool cmp1(int a,int b)
{
	return arr[a].l1<arr[b].l1;
}

bool cmp2(int a,int b)
{
	return arr[a].r1<arr[b].r1;
}

int get(int x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin()+1;
}

inline int add(int x,int y)
{
	int res=x+y;
	if(res<0) res+=MOD;
	if(res>=MOD) res-=MOD;
	return res;
}

void update(int node,int l,int r,int ind,int val)
{
	if(l==r)
	{
		btree[node]=val;
		return;
	}
	int mid=(l+r)/2;
	if(ind<=mid)
		update(node*2,l,mid,ind,val);
	else
		update(node*2+1,mid+1,r,ind,val);
	btree[node]=max(btree[node*2],btree[node*2+1]);
}


void update2(int node,int l,int r,int ind,int val)
{
	if(l==r)
	{
		stree[node]=val;
		return;
	}
	int mid=(l+r)/2;
	if(ind<=mid)
		update2(node*2,l,mid,ind,val);
	else
		update2(node*2+1,mid+1,r,ind,val);
	stree[node]=add(stree[node*2],stree[node*2+1]);
}

int query(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)/2;
	return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}

int query2(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return stree[node];
	int mid=(l+r)/2;
	return add(query2(node*2,l,mid,ql,qr),query2(node*2+1,mid+1,r,ql,qr));
}
vector< pair<int,int> > v;

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&arr[i].l1,&arr[i].r1,&arr[i].l2,&arr[i].r2);
		cmp.push_back(arr[i].l2); cmp.push_back(arr[i].r2);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	for(int i=0;i<n;i++)
	{
		arr[i].l2=get(arr[i].l2); arr[i].r2=get(arr[i].r2);
	}
	int m=cmp.size();
	iota(sortl,sortl+n,0); iota(sortr,sortr+n,0);
	sort(sortl,sortl+n,cmp1); sort(sortr,sortr+n,cmp2);
	int y=0;
	for(int i=0;i<n;i++)
	{
		int x=sortl[i];
		while(y<n&&arr[sortr[y]].r1<arr[x].l1)
		{
			//cout << "GOT: " << arr[sortr[y]].l1 << " " << arr[sortr[y]].r1 << " " << arr[sortr[y]].r2 << endl;
			update(1,0,m,arr[sortr[y]].r2,dp[sortr[y]]);
			y++;
		}
		dp[x]=1+query(1,0,m,0,arr[x].l2);
		/*cout << dp[x] << endl;
		cout << arr[x].l1 << " " << arr[x].r1 << " " << arr[x].l2 << " " << arr[x].r2 << endl;*/
	}
	int maxi=0;
	for(int i=0;i<n;i++)
		maxi=max(maxi,dp[i]);
	for(int i=0;i<n;i++)
	{
		v.push_back({dp[i],arr[i].r2});
	}
	sort(v.begin(),v.end());
	y=0;
	for(int i=0;i<n;i++)
	{
		int x=sortl[i];
		while(y<n&&arr[sortr[y]].r1<arr[x].l1)
		{
			//cout << "GOT: " << arr[sortr[y]].l1 << " " << arr[sortr[y]].r1 << " " << arr[sortr[y]].r2 << endl;
			int yy=sortr[y];
			int myind=lower_bound(v.begin(),v.end(),make_pair(dp[yy],arr[yy].r2))-v.begin();
			update2(1,0,n-1,myind,dpways[yy]);
			y++;
		}
		if(dp[x]==1)
		{
			dpways[x]=1;
			continue;
		}
		int myind=lower_bound(v.begin(),v.end(),make_pair(dp[x]-1,0))-v.begin();
		int rr=upper_bound(v.begin()+myind,v.end(),make_pair(dp[x]-1,arr[x].l2))-v.begin()-1;
		dpways[x]=query2(1,0,n-1,myind,rr);
		/*cout << dp[x] << endl;
		cout << arr[x].l1 << " " << arr[x].r1 << " " << arr[x].l2 << " " << arr[x].r2 << endl;*/
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(dp[i]==maxi) ans=add(ans,dpways[i]);
	}
	cout << maxi << " " << ans << endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
trapezoid.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&arr[i].l1,&arr[i].r1,&arr[i].l2,&arr[i].r2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100