oj.uz

Submission #525115

# Submission time Handle Problem Language Result Execution time Memory
525115 2022-02-10T18:14:57 Z mbfibat trapezoid (balkan11_trapezoid) C++17
100 / 100
 198 ms 32460 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 968 KB Output is correct
6 Correct 5 ms 1816 KB Output is correct
7 Correct 7 ms 1868 KB Output is correct
8 Correct 7 ms 1228 KB Output is correct
9 Correct 14 ms 2244 KB Output is correct
10 Correct 31 ms 8512 KB Output is correct
11 Correct 41 ms 8260 KB Output is correct
12 Correct 79 ms 17220 KB Output is correct
13 Correct 103 ms 20496 KB Output is correct
14 Correct 142 ms 32460 KB Output is correct
15 Correct 133 ms 17996 KB Output is correct
16 Correct 147 ms 22280 KB Output is correct
17 Correct 172 ms 29544 KB Output is correct
18 Correct 123 ms 21724 KB Output is correct
19 Correct 144 ms 28100 KB Output is correct
20 Correct 198 ms 27456 KB Output is correct