Submission #681925

#	Time	Username	Problem	Language	Result	Execution time	Memory
681925		badont	trapezoid (balkan11_trapezoid)	C++17	60 / 100	193 ms	65536 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

const LL INF = 1e9;

const LL MOD = 30013;
struct mint {
    int x;
    mint() : x(0) {}
    template <class T> mint(T value) : x(value % MOD) { if (x < 0) x += MOD; }
    mint & operator+=(const mint &oth) { x += oth.x; if (x >= MOD) x -= MOD; return *this; }
    mint & operator-=(const mint &oth) { x -= oth.x; if (x < 0) x += MOD; return *this; }
    mint & operator*=(const mint &oth) { x = (long long) x * oth.x % MOD; return *this; }
    friend mint operator+(mint l, const mint &r) { return l += r; }
    friend mint operator-(mint l, const mint &r) { return l -= r; }
    friend mint operator*(mint l, const mint &r) { return l *= r; }
    mint & operator--() { if (--x == -1) x = MOD - 1; return *this; }
    mint & operator++() { if (++x == MOD) x = 0; return *this; }
    mint operator--(int) { mint temp = *this; --*this; return temp; }
    mint operator++(int) { mint temp = *this; ++*this; return temp; }
    mint operator-() const { return 0 - *this; }
    mint operator+() const { return *this; }
    friend bool operator==(const mint &l, const mint &r) { return l.x == r.x; }
    friend bool operator!=(const mint &l, const mint &r) { return l.x != r.x; }
    friend ostream & operator<<(ostream &out, const mint &a) { return out << a.x; }
    mint pow(long long e = MOD - 2) const {
        mint ans = 1, b = *this;
        while (e > 0) {
            if (e % 2 == 1) {
                ans *= b;
            }
            b *= b;
            e /= 2;
        }
        return ans;
    }
};

struct Info {
	LL dp;
	mint ways;
	Info(LL dp, mint ways) : dp(dp), ways(ways) {}
};

Info max(const Info& a, const Info& b) {
	if (a.dp > b.dp) { return a; }
	if (b.dp > a.dp) { return b; }
	return Info(a.dp, a.ways + b.ways);
};

template<class T>
struct node {
	node* l;
	node* r;
	T val;
 
	node(T val) : l(nullptr), r(nullptr), val(val) {}
	node(node* l, node* r) : l(l), r(r), val(-INF, 0) {
		if (l) val = max(val, l->val);
		if (r) val = max(val, r->val);
	}
};
 
template<class T>
struct sex {
 
	LL nVal = 0;
 
	node<T>* build(vector<T>& a, int zl, int zr) {
		if (zl == zr) return new node<T>(a[zl]);
		int m = (zl + zr) >> 1;
		return new node<T>(build(a, zl, m), build(a, m + 1, zr));
	} 
 
	node<T>* build(vector<T>& a) {
		this->nVal = (int)a.size();
		return build(a, 0, (int)a.size() - 1);
	}
 
	node<T>* build(int n) {
		this->nVal = n;
		vector<T> res(n, -INF);
		return build(res, 0, n - 1);
	}
 
	node<T>* upd(node<T>* c, int zl, int zr, int pos, T new_val) {
		if (zl == zr) 
			return new node<T>(max(c->val, new_val));
		int m = (zl + zr) >> 1;
		if (pos <= m)
			return new node<T>(upd(c->l, zl, m, pos, new_val), c->r);
		else  
			return new node<T>(c->l, upd(c->r, m + 1, zr, pos, new_val));
	}
 
	T query(node<T>* c, int zl, int zr, int l, int r) {
		if (c == nullptr || l > r) 
			return T(-INF, 0);
 
		if (l <= zl && zr <= r) 
			return c->val;
 
		int m = (zl + zr) >> 1;
		T ret = max(query(c->l, zl, m, l, min(r, m)), 
				query(c->r, m + 1, zr, max(l, m + 1), r));
 
		return ret;
	};
};

void solve() {
	LL n;
	cin >> n;

	vector<array<LL, 4>> a(n);
	for (auto& [x, y, z, d] : a)
		cin >> x >> y >> z >> d;

	vector<LL> a_ricky, b_ricky;
	for (auto [x, y, z, d] : a) {
		a_ricky.pb(x);
		a_ricky.pb(y);
		b_ricky.pb(z);
		b_ricky.pb(d);
	}

	sort(all(a_ricky));
	sort(all(b_ricky));

	a_ricky.erase(unique(all(a_ricky)), a_ricky.end());
	b_ricky.erase(unique(all(b_ricky)), b_ricky.end());

	auto get_a = [&](const LL& g) -> LL {
		return lower_bound(all(a_ricky), g) - a_ricky.begin() + 1;
	};
	auto get_b = [&](const LL& g) -> LL {
		return lower_bound(all(b_ricky), g) - b_ricky.begin() + 1;
	};

	LL A = (int)a_ricky.size();
	LL B = (int)b_ricky.size();
	vector sweep(A + 1, vector<array<LL, 3>>());

	for (auto [x, y, z, d] : a) {
		sweep[get_a(y)].pb({get_a(x), get_b(z), get_b(d)});
	}

	//debug(sweep);

	sex<Info> tree;
	vector<Info> init(B + 1, Info(-INF, 0)); init[0] = Info(0, 1);

	vector<node<Info>*> roots = {(tree.build(init))};

	Info ans(-INF, 0);
	FOR (i, A) {
		node<Info>* recent = roots.back();
		for (auto [l, x, y] : sweep[i]) {
			node<Info>* rel = roots[l - 1];
			Info trans = tree.query(rel, 0, B, 0, x - 1);

			Info next = Info(trans.dp + 1, trans.ways);
			ans = max(ans, next);
			
			recent = tree.upd(recent, 0, B, y, next);
		}
		roots.push_back(recent);
	}

	cout << ans.dp << " " << ans.ways << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

 

• Subtask 1: 60 / 100