/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair
namespace custom_cp {
void setIO(const std::string &s = "", const std::string &in = ".in",
const std::string &out = ".out") {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
if (!s.empty()) {
freopen((s + in).c_str(), "r", stdin);
freopen((s + out).c_str(), "w", stdout);
}
}
} // namespace custom_cp
typedef std::array<int, 4> trapezoid;
typedef std::array<int, 3> query;
std::vector<int> st;
const int MOD = 30013;
void upd(const int &id, const int &l, const int &r, const int &p, const int &v,
std::function<int(int, int)> combine) {
if (l == r) {
st[id] = v;
return;
}
int m = (l + r) >> 1;
if (p <= m)
upd(id << 1, l, m, p, v, combine);
else
upd(id << 1 | 1, m + 1, r, p, v, combine);
st[id] = combine(st[id << 1], st[id << 1 | 1]);
return;
}
int get(const int &id, const int &l, const int &r, const int &u, const int &v,
std::function<int(int, int)> combine) {
if (r < u || l > v)
return 0;
if (l >= u && r <= v) {
return st[id];
}
int m = (l + r) >> 1;
return combine(get(id << 1, l, m, u, v, combine),
get(id << 1 | 1, m + 1, r, u, v, combine));
}
int get_max(const int &a, const int &b) { return std::max(a, b); }
int get_sum(const int &a, const int &b) { return (a + b) % MOD; }
int main() {
custom_cp::setIO();
int n;
std::cin >> n;
std::vector<trapezoid> v;
std::vector<int> compress;
for (int i = 0; i < n; i++) {
trapezoid t;
for (int j = 0; j < 4; j++) {
std::cin >> t[j];
compress.push_back(t[j]);
}
v.push_back(t);
}
std::sort(compress.begin(), compress.end());
compress.erase(std::unique(compress.begin(), compress.end()), compress.end());
auto get_compress = [&](const int &x) -> int {
return std::lower_bound(compress.begin(), compress.end(), x) -
compress.begin();
};
std::vector<query> queries;
for (int i = 0; i < n; i++) {
for (int &a : v[i])
a = get_compress(a);
queries.push_back({v[i][0], 0, i});
queries.push_back({v[i][1], 1, i});
}
std::sort(queries.begin(), queries.end());
const int sz = compress.size();
st = std::vector<int>((sz << 2) + 5, 0);
std::vector<std::pair<int, int>> lis(n, {0, 0});
for (int i = 0; i < n; i++) {
lis[i].ff = 1;
lis[i].ss = i;
}
for (const query &q : queries) {
int type = q[1];
if (type) {
upd(1, 0, sz - 1, v[q[2]][3], lis[q[2]].ff, &get_max);
} else {
if (v[q[2]][2])
lis[q[2]].ff = get(1, 0, sz - 1, 0, v[q[2]][2] - 1, &get_max) + 1;
}
}
std::fill(st.begin(), st.end(), 0);
int longest = 1;
for (int i = 0; i < n; i++)
longest = std::max(longest, lis[i].ff);
std::vector<std::vector<int>> order(longest);
for (const std::pair<int, int> &p : lis) {
order[p.ff - 1].push_back(p.ss);
}
std::vector<int> dp(n, 1);
for (int i = 0; i < longest - 1; i++) {
queries = std::vector<query>();
for (const int &j : order[i]) {
queries.push_back({v[j][0], 0, j});
queries.push_back({v[j][1], 1, j});
}
for (const int &j : order[i + 1]) {
queries.push_back({v[j][0], 0, j});
queries.push_back({v[j][1], 1, j});
}
sort(queries.begin(), queries.end());
for (const query &q : queries) {
int type = q[1];
if (type) {
upd(1, 0, sz - 1, v[q[2]][3], dp[q[2]], &get_sum);
} else {
if (v[q[2]][2] && lis[q[2]].ff == i + 2)
dp[q[2]] =
std::max(1, get(1, 0, sz - 1, 0, v[q[2]][2] - 1, &get_sum));
}
}
for (const int &j : order[i]) {
upd(1, 0, sz - 1, v[j][3], 0, &get_sum);
}
for (const int &j : order[i + 1]) {
upd(1, 0, sz - 1, v[j][3], 0, &get_sum);
}
// std::cout << "Reset test" << ' ' << get(1, 0, sz - 1, 0, sz - 1,
// &get_sum)
// << '\n';
}
int ways = 0;
for (int i = 0; i < n; i++) {
if (lis[i].ff == longest)
ways = get_sum(ways, dp[i]);
}
std::cout << longest << ' ' << ways << '\n';
}
Compilation message (stderr)
trapezoid.cpp: In function 'void custom_cp::setIO(const string&, const string&, const string&)':
trapezoid.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen((s + in).c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | freopen((s + out).c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
