oj.uz

Submission #861756

# Submission time Handle Problem Language Result Execution time Memory
861756 2023-10-17T01:43:15 Z x0r trapezoid (balkan11_trapezoid) C++17
70 / 100
 336 ms 65536 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 = 2e6;
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
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33624 KB Output is correct
2 Correct 7 ms 33628 KB Output is correct
3 Correct 7 ms 33628 KB Output is correct
4 Correct 7 ms 33628 KB Output is correct
5 Correct 9 ms 33628 KB Output is correct
6 Correct 11 ms 33680 KB Output is correct
7 Correct 13 ms 33884 KB Output is correct
8 Correct 15 ms 33880 KB Output is correct
9 Correct 24 ms 34196 KB Output is correct
10 Correct 41 ms 34776 KB Output is correct
11 Correct 58 ms 34840 KB Output is correct
12 Correct 104 ms 35816 KB Output is correct
13 Correct 123 ms 36292 KB Output is correct
14 Correct 147 ms 37832 KB Output is correct
15 Runtime error 317 ms 65536 KB Execution killed with signal 9
16 Runtime error 313 ms 65536 KB Execution killed with signal 9
17 Runtime error 333 ms 65536 KB Execution killed with signal 9
18 Runtime error 300 ms 65536 KB Execution killed with signal 9
19 Runtime error 328 ms 65536 KB Execution killed with signal 9
20 Runtime error 336 ms 65536 KB Execution killed with signal 9