oj.uz

Submission #861755

# Submission time Handle Problem Language Result Execution time Memory
861755 2023-10-17T01:41:45 Z x0r trapezoid (balkan11_trapezoid) C++17
0 / 100
 33 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 = 1e7;
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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 65536 KB Execution killed with signal 9
2 Runtime error 16 ms 65536 KB Execution killed with signal 9
3 Runtime error 16 ms 65536 KB Execution killed with signal 9
4 Runtime error 16 ms 65536 KB Execution killed with signal 9
5 Runtime error 32 ms 65536 KB Execution killed with signal 9
6 Runtime error 16 ms 65536 KB Execution killed with signal 9
7 Runtime error 15 ms 65536 KB Execution killed with signal 9
8 Runtime error 16 ms 65536 KB Execution killed with signal 9
9 Runtime error 14 ms 65536 KB Execution killed with signal 9
10 Runtime error 33 ms 65536 KB Execution killed with signal 9
11 Runtime error 15 ms 65536 KB Execution killed with signal 9
12 Runtime error 32 ms 65536 KB Execution killed with signal 9
13 Runtime error 14 ms 65536 KB Execution killed with signal 9
14 Runtime error 16 ms 65536 KB Execution killed with signal 9
15 Runtime error 19 ms 65536 KB Execution killed with signal 9
16 Runtime error 18 ms 65536 KB Execution killed with signal 9
17 Runtime error 14 ms 65536 KB Execution killed with signal 9
18 Runtime error 16 ms 65536 KB Execution killed with signal 9
19 Runtime error 18 ms 65536 KB Execution killed with signal 9
20 Runtime error 16 ms 65536 KB Execution killed with signal 9