Submission #97759

#	Time	Username	Problem	Language	Result	Execution time	Memory
97759		Anai	trapezoid (balkan11_trapezoid)	C++14	85 / 100	572 ms	29020 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
 
#define fi cin
#define fo cout
 
using pii = pair<int, int>;
 
const int N = 1e5 + 5, MOD = 30013;
 
struct Point {
	int idx, x, y;
	bool cap; };
 
pii dp[N], pom[N * 16];
 
vector<Point> pts;
pii qval;
int n, bnd, ql, qr, qpos;
 
static int fix(int arg) {
	return arg >= MOD ? arg - MOD : arg; }
 
static pii join(const pii &a, const pii &b) {
	if (a.first > b.first)
		return a;
	if (a.first < b.first)
		return b;
	return pii(a.first, fix(a.second + b.second)); }
 
static pii query(int nod, int st, int dr) {
	if (ql <= st && dr <= qr)
		return pom[nod];
	int mid = (st + dr) / 2;
	pii l = (ql <= mid ? query(2 * nod, st, mid) : pii(0, 0));
	pii r = (mid < qr ? query(2 * nod + 1, mid + 1, dr) : pii(0, 0));
	return join(l, r); }
 
static void update(int nod, int st, int dr) {
	if (st == dr) {
		pom[nod] = (pom[nod].first == qval.first ? pii(qval.first, qval.second + pom[nod].second) : qval);
		pom[nod].second = fix(pom[nod].second);
		return; }
	int mid = (st + dr) / 2;
	if (qpos <= mid)
		update(2 * nod, st, mid);
	else
		update(2 * nod + 1, mid + 1, dr);
	pom[nod] = join(pom[2 * nod], pom[2 * nod + 1]); }
 
static void normalize() {
	map<int, int> mp;
	int idx = 0;
	for (auto i: pts)
		mp[i.x] = mp[i.y] = 0;
	for (auto &i: mp)
		i.second = ++idx;
	for (auto &i: pts) {
		i.x = mp[i.x];
		i.y = mp[i.y]; }
	bnd = mp.size(); }
 
static char nextch() {
	const int BMAX = 1 << 17;
	static char buff[BMAX];
	static int bp = BMAX;
	if (bp == BMAX) {
		fread(buff, 1, BMAX, stdin);
		bp = 0; }
	return buff[bp++]; }
 
static void get(int &x) {
	char ch;
	do {
		ch = nextch(); }
	while (ch < '0' || '9' < ch);
	x = 0;
	do {
		x = x * 10 + (ch - '0');
		ch = nextch(); }
	while ('0' <= ch && ch <= '9'); }
 
int main() {
	int crd, cnt;
 
	get(n);
	pts.reserve(n);
	for (int i = 0; i < n; ++i) {
		int a, b, c, d;
		get(a), get(b), get(c), get(d);
		pts.push_back({i, a, c, 1});
		pts.push_back({i, b, d, 0}); }
 
	normalize();
	sort(begin(pts), end(pts), [&](const Point &a, const Point &b) {
		return pii(a.x, a.y) < pii(b.x, b.y); });
 
	for (const auto &i: pts) {
		if (i.cap) {
			ql = 1, qr = i.y;
			dp[i.idx] = query(1, 1, bnd);
			if (++dp[i.idx].first == 1)
				dp[i.idx].second = 1;}
		else {
			qpos = i.y;
			qval = dp[i.idx];
			update(1, 1, bnd); } }
 
	crd = cnt = 0;
	for (int i = 0; i < n; ++i)
		crd = max(crd, dp[i].first);
	for (int i = 0; i < n; ++i)
		if (dp[i].first == crd)
			cnt = fix(cnt + dp[i].second);
 
	printf("%d %d\n", crd, cnt);
 
	return 0; }

Compilation message (stderr)

trapezoid.cpp: In function 'char nextch()':
trapezoid.cpp:68:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fread(buff, 1, BMAX, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 85 / 100