Submission #379253

#	Time	Username	Problem	Language	Result	Execution time	Memory
379253		Cantfindme	trapezoid (balkan11_trapezoid)	C++17	100 / 100	335 ms	43024 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 30013;

int n;
struct trap {
	int a,b, c, d;
};

trap A[maxn];
vector <pii> v;
vector <int> pp;

struct node {
	int s,m,e;
	int maxv;
	int ways;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e;
		m = (s+e)/2;
		maxv = ways = 0;
		
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}				
	}
	
	void up(int x, int vv) {
		if (s == e) {
			maxv = vv;
			return;
		} 
		if (x > m) r -> up(x,vv);
		else l -> up(x,vv);
		maxv = max(l -> maxv, r -> maxv);
	}
	
	int rmq(int x, int y) {
		if (s == x and e == y) return maxv;
		else if (x > m) return r -> rmq(x,y);
		else if (y <= m) return l -> rmq(x,y);
		else return max(l -> rmq(x,m), r -> rmq(m+1,y));
	}
	
	void up2(int x, int vv) {
		if (s == e) {
			ways = vv;
			return;
		}
		if (x > m) r -> up2(x,vv);
		else l -> up2(x,vv);
		ways = (l -> ways + r -> ways) % mod;
	}
	
	int sum(int x, int y) {
		if (s == x and e == y) return ways;
		else if (x > m) return r -> sum(x,y);
		else if (y <= m) return l -> sum(x,y);
		else return (l -> sum(x,m) + r -> sum(m+1,y)) % mod;
	}
}*root;

vector <int> vec2[maxn];
int mp[maxn];
int waysans[maxn];

int32_t main() {
	FAST
	cin >> n;
	for (int i =0;i<n;i++) {
		int a,b,c,d; cin >> a >> b >> c >> d;
		A[i] = {a,b,c,d};
		v.push_back(pii(a,pi(0,i)));
		v.push_back(pii(b,pi(1,i)));
		pp.push_back(c);
		pp.push_back(d);
	}
	pp.push_back(0);
	
	sort(all(pp));
	pp.resize(unique(all(pp)) - pp.begin());
	
	sort(all(v));
	root = new node(0,pp.size()+1);
	
	for (auto [x, cur] : v) {
		auto [type, indx] = cur;
		if (type == 0) {
			int lb = lower_bound(all(pp), A[indx].c) - pp.begin();
			
			int best = root -> rmq(0, lb);
			mp[indx] = best + 1;	
			vec2[mp[indx]].push_back(indx);		
		} else {
			int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
			
			root -> up(lb, mp[indx]);
		}
	}
	
	int ans = root -> rmq(0, pp.size());
	root -> up2(0, 1);
	
	for (int i = 1;i<=ans;i++) {
		vector <pii> vv;
		
		for (auto indx: vec2[i-1]) {
			vv.push_back(pii(A[indx].b, pi(0,indx)));
		}
		
		for (auto indx: vec2[i]) {
			vv.push_back(pii(A[indx].a, pi(1,indx)));
		}
		
		sort(all(vv));
		
		for (auto [x, cur] : vv) {
			auto [type, indx] = cur;
			if (type == 0) {
				int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
				root -> up2(lb, waysans[indx]);
			} else {
				int lb = lower_bound(all(pp), A[indx].c) - pp.begin();
				int total = root -> sum(0,lb);
				waysans[indx] = total;
			}
		}
		
		for (auto indx: vec2[i-1]) {
			int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
			root -> up2(lb, 0);
		}
		
		if (i == 1)  {
			root -> up2(0, 0);
		}
	}
	
	int rans = 0;
	for (auto indx: vec2[ans]) {
		rans += waysans[indx];
		rans %= mod;
	}
	cout << ans << " " << rans;
}

• Subtask 1: 100 / 100