Submission #1346788

#TimeUsernameProblemLanguageResultExecution timeMemory
1346788jahongirtrapezoid (balkan11_trapezoid)C++20
100 / 100
63 ms9112 KiB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

typedef pair<int,int> pii;

const int mod = 30013;


namespace SegTree{
	
	pii operator+(const pii &a, const pii &b){
		pii res = {max(a.first,b.first),0};
		if(res.first==a.first) res.second += a.second;
		if(res.first==b.first) res.second += b.second;
		if(res.second >= mod) res.second -= mod;
		return res;
	}

	pii st[1<<19];
	
	void init(){
		fill(st,st+(1<<19),pii{-1,0});
	}

	void add(int i, int l, int r, int k, pii v){
		if(l==r){st[i]=v; return;}
		int m = (l+r)>>1;
		if(k <= m) add(i<<1,l,m,k,v);
		else add(i<<1|1,m+1,r,k,v);
		st[i] = st[i<<1] + st[i<<1|1];
	}

	pii get(int i, int l, int r, int s, int e){
		if(r < s || l > e) return {-1,0};
		if(s <= l && r <= e) return st[i];
		int m = (l+r)>>1;
		return get(i<<1,l,m,s,e) + get(i<<1|1,m+1,r,s,e);
	}

}


signed main(){
	cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;

	vector<pii> up,low;

	for(int i = 0; i < n; i++){
		int a,b,c,d; cin >> a >> b >> c >> d;
		up.emplace_back(a,i);
		up.emplace_back(b,i+n);
		low.emplace_back(c,i);
		low.emplace_back(d,i+n);
	}

	sort(up.begin(),up.end());
	sort(low.begin(),low.end());

	vector<int> ind(2*n);
	vector<pii> dp(n);
	for(int i = 0; i < 2*n; i++)
		ind[low[i].second] = i;
	
	SegTree::init();

	SegTree::add(1,0,2*n,0,{0,1});
		
	for(auto [x,i] : up){
		if(i < n){
			dp[i] = SegTree::get(1,0,2*n,0,ind[i]+1);
			dp[i].first++;
		}else{
			SegTree::add(1,0,2*n,ind[i]+1,dp[i-n]);
		}
	}
	
	cout << SegTree::st[1].first << ' ' << SegTree::st[1].second << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...