Submission #861757

#	Time	Username	Problem	Language	Result	Execution time	Memory
861757		x0r	trapezoid (balkan11_trapezoid)	C++17	100 / 100	218 ms	53692 KiB

trapezoid

#include <bits/stdc++.h>

#define pii pair < int, int >
#define fi first
#define se second
#define pb push_back

using namespace std;

const int NMAX = 1E5;
const int N = 3e6;
const int INF = 1E9 + 7;
const int MOD = 30013;

struct Trapezoid {
	pii up, down;
	Trapezoid() {
		up = down = {0, 0};
	}
} a[NMAX + 3];

int root[NMAX + 3];

int n, nnode = 0;

vector < int > compress;

struct Node {
	pii val;
	int l, r;
	Node() {
		val = {0, 0}; l = r = 0;
	}
	Node (pii x) {
		val = x; l = r = 0;
	}
} it[N + 3];

pii merge(const pii &x, const pii &y) {
	if (x.fi > y.fi) return x;
	if (x.fi < y.fi) return y;
	return {x.fi, (x.se + y.se) % MOD};
}

int build(int l, int r) {
	if (l == r) {
		if (l == 0) it[++ nnode].val = {0, 1};
		else it[++ nnode].val = {0, 0};
		return nnode;
	}
	int mid = (l + r) / 2, cur = ++ nnode;
	it[cur].l = build(l, mid); it[cur].r = build(mid + 1, r);
	it[cur].val = merge(it[it[cur].l].val, it[it[cur].r].val);
	return cur;
}

pii query(int node, int l, int r, int u, int v) {
	//cout << l << " " << r << " " << u << " " << v << " " << it[node].val.fi << " " << it[node].val.se << '\n';
	if (v < l || r < u) return {0, 0};
	if (u <= l && r <= v) return it[node].val;
	int mid = (l + r) / 2;
	return merge(query(it[node].l, l, mid, u, v), query(it[node].r, mid + 1, r, u, v));
}

int update(int node, int l, int r, int u, pii val) {
	if (l == r) {
		it[++ nnode].val = merge(it[node].val, val);
		return nnode;
	}
	int mid = (l + r) / 2, cur = ++nnode;
	if (u <= mid) {
		it[cur].l = update(it[node].l, l, mid, u, val);
		it[cur].r = it[node].r;
	}
	else {
		it[cur].l = it[node].l;
		it[cur].r = update(it[node].r, mid + 1, r, u, val);
	}
	it[cur].val = merge(it[it[cur].l].val, it[it[cur].r].val);
	return cur;
}

int main() {
	cin >> n;
	compress.pb(-INF);
	for (int i = 1; i <= n; i++) {
		cin >> a[i].up.fi >> a[i].up.se >> a[i].down.fi >> a[i].down.se;
		compress.pb(a[i].up.fi);
		compress.pb(a[i].up.se);
		compress.pb(a[i].down.fi);
		compress.pb(a[i].down.se);
	}
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
	for (int i = 1; i <= n; i++) {
		a[i].up.fi = lower_bound(compress.begin(), compress.end(), a[i].up.fi) - compress.begin();
		a[i].up.se = lower_bound(compress.begin(), compress.end(), a[i].up.se) - compress.begin();
		a[i].down.fi = lower_bound(compress.begin(), compress.end(), a[i].down.fi) - compress.begin();
		a[i].down.se = lower_bound(compress.begin(), compress.end(), a[i].down.se) - compress.begin();
	}
	sort(a + 1, a + n + 1, [&](Trapezoid &x, Trapezoid &y) {
		return x.down.se < y.down.se;
	});
	a[0].up = {-INF, -INF}; a[0].down = {-INF, -INF};
	root[0] = build(0, 4 * n);
	pii res = {0, 0};
	for (int i = 1; i <= n; i++) {
		int l = 0, r = i - 1, mid, ans;
		while (l <= r) {
			mid = (l + r) / 2;
			if (a[mid].down.se < a[i].down.fi) {
				ans = mid;
				l =  mid + 1;
			}
			else r = mid - 1;
		} 
		pii temp = query(root[ans], 0, 4 * n, 0, a[i].up.fi - 1); temp.fi ++;
		res = merge(res, temp);
		root[i] = update(root[i - 1], 0, 4 * n, a[i].up.se, temp);
		// cout << i << " " << temp.fi << " " << temp.se << '\n';
	}
	cout << res.fi << " " << res.se;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:117:58: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |   pii temp = query(root[ans], 0, 4 * n, 0, a[i].up.fi - 1); temp.fi ++;
      |                                                          ^

• Subtask 1: 100 / 100