Submission #525115

#	Time	Username	Problem	Language	Result	Execution time	Memory
525115		mbfibat	trapezoid (balkan11_trapezoid)	C++17	100 / 100	198 ms	32460 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

const int mod = 30013;

struct Trapezoid {
	int x1, x2, y1, y2;
	Trapezoid(){}
};

istream& operator>>(istream& cin, Trapezoid& cur) {
	cin >> cur.x1 >> cur.x2 >> cur.y1 >> cur.y2;
	return cin;
}

bool operator<(const Trapezoid& lhs, const Trapezoid& rhs) {
	return lhs.x1 < rhs.x1;
}

typedef struct Node* pNode;

struct Node {
	int mx, sum;
	pNode l, r;
	Node () {
		mx = 0, sum = 0;
		l = r = nullptr;
	}
};

ii cal(const ii& lhs, const ii& rhs) {
	ii data;
	if (lhs.first > rhs.first)
		data = lhs;
	else if (lhs.first < rhs.first)
		data = rhs;
	else {
		data.first = lhs.first;
		data.second = (lhs.second + rhs.second) % mod;
	}	
	return data;
}

void update(pNode& root, int l, int r, int pos, int f, int cnt) {
	if (!root) root = new Node();
	if (l == r) {
		root -> mx = f, root -> sum = cnt;
		return;
	}	

	int mi = (l + r)/2;
	if (pos <= mi) update(root -> l, l, mi, pos, f, cnt);
	else update(root -> r, mi + 1, r, pos, f, cnt);

	if (!root -> l) root -> l = new Node();
	if (!root -> r) root -> r = new Node();
	ii lhs = ii(root -> l -> mx, root -> l -> sum);
	ii rhs = ii(root -> r -> mx, root -> r -> sum);
	ii data = cal(lhs, rhs); root -> mx = data.first; root -> sum = data.second;
}

ii query(pNode &root, int l, int r, int ll, int rr) {
	if (!root) root = new Node();
	if (r < ll || rr < l) return ii(0, 0);
	if (ll <= l && r <= rr) return ii(root -> mx, root -> sum);

	int mi = (l + r)/2;
	ii lhs = query(root -> l, l, mi, ll, rr);
	ii rhs = query(root -> r, mi + 1, r, ll, rr);
	return cal(lhs, rhs);
}

int n;
Trapezoid a[100001];

int f[100001], cnt[100001];

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)	
		cin >> a[i];
	sort(a + 1, a + 1 + n);

	pNode root = new Node();
	set<ii> upd;

	update(root, 0, 1e9, 0, 0, 1);
	for (int i = 1; i <= n; i++) {
		while (!upd.empty() && (*upd.begin()).first < a[i].x1) {
			// Update
			int id = (*upd.begin()).second;
			update(root, 0, 1e9, a[id].y2, f[id], cnt[id]);
			upd.erase(upd.begin());
		}
		
		ii data = query(root, 0, 1e9, 0, a[i].y1 - 1);
		f[i] = data.first + 1, cnt[i] = data.second;

		upd.insert(ii(a[i].x2, i));
	}

	int ans_mx = *max_element(f + 1, f + 1 + n);
	int ans_cnt = 0;
	for (int i = 1; i <= n; i++)
		if (f[i] == ans_mx)
			(ans_cnt += cnt[i]) %= mod;

//	for (int i = 1; i <= n; i++) {
//		cerr << a[i].x1 << ' ' << a[i].x2 << ' ' << a[i].y1 << ' ' << a[i].y2 << "!" << f[i] << ' ' << cnt[i] << '\n';
//	}
	cout << ans_mx << ' ' << ans_cnt << '\n';
}

• Subtask 1: 100 / 100