Submission #1222878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222878		boclobanchat	trapezoid (balkan11_trapezoid)	C++20	100 / 100	98 ms	10504 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
struct query { int t,i,pos,p; };
bool sortq(query a,query b) { if(a.pos==b.pos) return a.t<b.t;return a.pos<b.pos; }
const int MAXN=5e5+5;
const int mod=30013;
int val[MAXN],A[MAXN][4];
query Q[MAXN*2];
ii fen[MAXN],num[MAXN];
ii merge(ii a,ii b)
{
	if(a.fi<b.fi) return b;
	if(a.fi>b.fi) return a;
	return {a.fi,(a.se+b.se)%mod};
}
void update(int i,ii val) { for(;i<MAXN;i+=i&-i) fen[i]=merge(fen[i],val); }
ii get(int i) { ii ans={0,1};for(;i;i-=i&-i) ans=merge(ans,fen[i]);return ans; }
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>k;
	int cnt=0,cv=0;
	for(int i=1;i<=k;i++)
	{
		int l,r,u,v;
		cin>>l>>r>>u>>v;
		val[++cv]=l,val[++cv]=r,val[++cv]=u,val[++cv]=v;
		A[i][0]=l,A[i][1]=r,A[i][2]=u,A[i][3]=v;
	}
	sort(val+1,val+cv+1);
	for(int i=1;i<=k;i++)
	{
		int l=lower_bound(val+1,val+cv+1,A[i][0])-val;
		int r=lower_bound(val+1,val+cv+1,A[i][1])-val;
		int u=lower_bound(val+1,val+cv+1,A[i][2])-val;
		int v=lower_bound(val+1,val+cv+1,A[i][3])-val;
		Q[++cnt]={2,l-1,u-1,i};
		Q[++cnt]={1,r,v,i};
	}
	stack<ii> st;
	sort(Q+1,Q+cnt+1,sortq);
	num[0]={0,1};
	for(int i=1;i<=cnt;i++)
	{
		if(Q[i].t==1) st.push({Q[i].i,Q[i].p});
		else
		{
			ii res=get(Q[i].i);
			num[Q[i].p]={res.fi+1,res.se};
		}
		if(Q[i+1].t!=1)
		{
			while(!st.empty())
			{
				int a=st.top().fi,b=st.top().se;
				st.pop();
				update(a,num[b]);
			}
		}
	}
	cout<<get(cv).fi<<" "<<get(cv).se;
}

• Subtask 1: 100 / 100