oj.uz

Submission #583223

# Submission time Handle Problem Language Result Execution time Memory
583223 2022-06-25T06:09:54 Z willi19 trapezoid (balkan11_trapezoid) C++17
100 / 100
 130 ms 15084 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 5 ms 4792 KB Output is correct
7 Correct 6 ms 4920 KB Output is correct
8 Correct 8 ms 5060 KB Output is correct
9 Correct 13 ms 5492 KB Output is correct
10 Correct 19 ms 6664 KB Output is correct
11 Correct 25 ms 7020 KB Output is correct
12 Correct 60 ms 9764 KB Output is correct
13 Correct 75 ms 10724 KB Output is correct
14 Correct 88 ms 13664 KB Output is correct
15 Correct 102 ms 13448 KB Output is correct
16 Correct 126 ms 13428 KB Output is correct
17 Correct 115 ms 13648 KB Output is correct
18 Correct 89 ms 14200 KB Output is correct
19 Correct 101 ms 14656 KB Output is correct
20 Correct 130 ms 15084 KB Output is correct