oj.uz

Submission #861757

# Submission time Handle Problem Language Result Execution time Memory
861757 2023-10-17T01:43:52 Z x0r trapezoid (balkan11_trapezoid) C++17
100 / 100
 218 ms 53692 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 49244 KB Output is correct
2 Correct 9 ms 49308 KB Output is correct
3 Correct 10 ms 49280 KB Output is correct
4 Correct 10 ms 49244 KB Output is correct
5 Correct 13 ms 49420 KB Output is correct
6 Correct 15 ms 49364 KB Output is correct
7 Correct 16 ms 49244 KB Output is correct
8 Correct 17 ms 49532 KB Output is correct
9 Correct 27 ms 49756 KB Output is correct
10 Correct 43 ms 49880 KB Output is correct
11 Correct 54 ms 49880 KB Output is correct
12 Correct 109 ms 50380 KB Output is correct
13 Correct 130 ms 50380 KB Output is correct
14 Correct 150 ms 51400 KB Output is correct
15 Correct 167 ms 53212 KB Output is correct
16 Correct 181 ms 53184 KB Output is correct
17 Correct 187 ms 53444 KB Output is correct
18 Correct 173 ms 53420 KB Output is correct
19 Correct 206 ms 53540 KB Output is correct
20 Correct 218 ms 53692 KB Output is correct