Submission #650860

#	Time	Username	Problem	Language	Result	Execution time	Memory
650860		GusterGoose27	trapezoid (balkan11_trapezoid)	C++11	100 / 100	197 ms	37448 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MOD = 30013;
int n;
pii left_edge[MAXN];
pii right_edge[MAXN];
map<int, int> convert;
vector<int> top_coords;

class stree {
public:
	stree *l = nullptr;
	stree *r = nullptr;
	int lp, rp;
	pii opt; // max, ways_to_achieve
	stree(int lv, int rv) {
		opt = pii(0, 0);
		lp = lv;
		rp = rv;
		if (lp != rp) {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
		}
	}
	pii comb(pii a, pii b) {
		if (a.first == b.first) return pii(a.first, (a.second+b.second) % MOD);
		return max(a, b);
	}
	void comb() {
		opt = comb(l->opt, r->opt);
	}
	void update(int p, pii v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			opt = v;
			return;
		}
		l->update(p, v);
		r->update(p, v);
		comb();
	}
	pii query(int lv, int rv) {
		if (lp > rv || rp < lv) return pii(0, 0);
		if (lp >= lv && rp <= rv) return opt;
		return comb(l->query(lv, rv), r->query(lv, rv));
	}
};

class edge {
public:
	int b_point;
	int t_point;
	int id;
	int l_or_r; // l is 1, r is 0
	edge() {}
	edge(int b, int t, int i, int lr) : b_point(b), t_point(t), id(i), l_or_r(lr) {}
};

bool operator<(edge &a, edge &b) {
	return (a.b_point > b.b_point);
}

edge edges[2*MAXN];
pii dp_query[MAXN];
stree *tree;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		left_edge[i] = pii(a, c);
		right_edge[i] = pii(b, d);
		top_coords.push_back(a);
		top_coords.push_back(b);
	}
	sort(top_coords.begin(), top_coords.end());
	for (int t = 0; t < top_coords.size(); t++) convert[top_coords[t]] = t;
	for (int i = 0; i < n; i++) {
		left_edge[i].first = convert[left_edge[i].first];
		right_edge[i].first = convert[right_edge[i].first];
		edges[2*i] = edge(left_edge[i].second, left_edge[i].first, i, 1);
		edges[2*i+1] = edge(right_edge[i].second, right_edge[i].first, i, 0);
	}
	sort(edges, edges+2*n);
	tree = new stree(0, 2*n);
	tree->update(2*n, pii(0, 1));
	for (int i = 0; i < 2*n; i++) {
		if (edges[i].l_or_r) tree->update(edges[i].t_point, dp_query[edges[i].id]);
		else {
			dp_query[edges[i].id] = tree->query(edges[i].t_point+1, 2*n);
			dp_query[edges[i].id].first++;
		}
	}
	pii ans = tree->query(0, 2*n);
	cout << ans.first << " " << ans.second << "\n";
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int t = 0; t < top_coords.size(); t++) convert[top_coords[t]] = t;
      |                  ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100