#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
512 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1408 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 8 |
Correct |
16 ms |
1536 KB |
Output is correct |
| 9 |
Correct |
30 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
58 ms |
4676 KB |
Output is correct |
| 11 |
Correct |
101 ms |
8172 KB |
Output is correct |
| 12 |
Correct |
256 ms |
15768 KB |
Output is correct |
| 13 |
Correct |
354 ms |
18508 KB |
Output is correct |
| 14 |
Correct |
410 ms |
24736 KB |
Output is correct |
| 15 |
Correct |
421 ms |
19692 KB |
Output is correct |
| 16 |
Execution timed out |
502 ms |
21348 KB |
Time limit exceeded |
| 17 |
Execution timed out |
535 ms |
28236 KB |
Time limit exceeded |
| 18 |
Correct |
214 ms |
18424 KB |
Output is correct |
| 19 |
Correct |
445 ms |
27684 KB |
Output is correct |
| 20 |
Execution timed out |
572 ms |
29020 KB |
Time limit exceeded |
