Submission #583223

#	Time	Username	Problem	Language	Result	Execution time	Memory
583223		willi19	trapezoid (balkan11_trapezoid)	C++17	100 / 100	130 ms	15084 KiB

trapezoid

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

typedef long long ll;
typedef pair<ll,ll> pll;

const ll MX = 1<<17;
const ll INF = 1e18;
const ll mod = 30013;

#define f first
#define s second
#define pb push_back

ll n;
vector<pair<pll,ll> > query; //up, down, index, if down<0 in, else out
vector<ll> ind; //upper_bound-1, values of down out(right) values
pll mv[MX];

template<class T, ll SZ> struct mintree//with range update
{
	T mx[2*SZ];
	vector<ll> index;
	
	void init(ll l,ll r,ll ind)
	{
		if(l==r)
		{
			mx[ind].f = 0;
			mx[ind].s = 0;
			return;
		}
		ll mid = (l+r)>>1;
		init(l,mid,ind*2);
		init(mid+1,r,ind*2+1);
		mx[ind] = merge(mx[ind*2],mx[ind*2+1]);
	}
	
	T merge(T left, T right)
	{
		T ret;
		ret.f = max(left.f,right.f);
		if(left.f>right.f)
			ret.s = left.s;
		else if(left.f<right.f)
			ret.s = right.s;
		else
			ret.s = (left.s+right.s)%mod;
		return ret;
	}
	
	void set_index(vector<ll> &idx)
	{
		index = idx;
		init(0,n-1,1);
	}
	
	void update(ll l,ll r,ll x,T val, ll ind)
	{
		if(x<l||r<x)
			return;
		
		if(l==r)
		{
			mx[ind] = merge(mx[ind],val);
			return;
		}

		ll mid = (l+r)>>1;
		if(x<=mid) update(l,mid,x,val,ind*2);
		else update(mid+1,r,x,val,ind*2+1);
		mx[ind] = merge(mx[ind*2],mx[ind*2+1]);
	}
	
	T query(ll l,ll r,ll s,ll e, ll ind)
	{
		if(e<l || r<s)
			return {0,0};
		if(s<=l&&r<=e)
			return mx[ind];
		ll mid = (l+r)>>1;
		return merge(query(l,mid,s,e,ind*2),query(mid+1,r,s,e,ind*2+1));
	}
	
	void update(ll y,T v) //exit y and decrease value
	{
		ll ind = lower_bound(index.begin(),index.end(),y)-index.begin();
		update(0,n-1,ind,v,1);
	}
	
	T query(ll y)
	{
		ll ind = upper_bound(index.begin(),index.end(),y)-index.begin()-1;
		return query(0,n-1,0,ind,1);
	}
};

mintree<pll,MX> mt;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n;
	for(ll i=0;i<n;i++)
	{
		ll ul,ur,dl,dr;
		cin>>ul>>ur>>dl>>dr;
		query.push_back({{ul,-dl},i});//in, query
		query.push_back({{ur,dr},i});//out, update
		ind.push_back(dr);
	}
	
	sort(ind.begin(),ind.end());
	sort(query.begin(),query.end());
	
	mt.set_index(ind);
	for(auto q:query)
	{
		if(q.f.s<0)//in, query
		{
			pll ret = mt.query(-q.f.s);
			if(!ret.f) ret = {0,1};
			ret.f++;
			mv[q.s] = ret;
			//cout<<q.s<<" "<<ret.f<<" "<<ret.s<<"\n";
		}
		else
			mt.update(q.f.s,mv[q.s]);
	}
	pll ans = {0,0};
	for(ll i=0;i<n;i++)
		ans = mt.merge(ans,mv[i]);
	cout<<ans.f<<" "<<ans.s;
}

• Subtask 1: 100 / 100