/**
* Author : Nguyen Tuan Vu
* Created : 03.12.2022
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e5 + 5;
const int Mod = 30013;
int n;
pair <int, int> res[N];
struct RECTANGLE {
int a, b, c, d;
} a[N];
struct LINE {
int up, down, id, type;
LINE() {}
LINE(int up, int down, int id, int type) {
this->up = up;
this->down = down;
this->id = id;
this->type = type;
}
friend bool operator < (LINE &x, LINE &y) {
if (x.up != y.up) return x.up < y.up;
if (x.id != y.id) return x.type < y.type;
return x.type > y.type;
}
};
vector <LINE> line;
void add(int &x, int K) {
x += K;
if (x >= Mod) x -= Mod;
}
struct Fenwick_Tree {
int n;
vector <pair <int, int>> bit;
Fenwick_Tree(int n) {
this->n = n;
bit.resize(n + 7, make_pair(0, 0));
}
void update(int u, pair <int, int> val) {
for (; u <= n; u += u & -u) if (bit[u].first < val.first) {
bit[u] = val;
}
else if (bit[u].first == val.first) {
add(bit[u].second, val.second);
}
}
pair <int, int> get(int u) {
pair <int, int> ans = make_pair(0, 0);
for (; u; u -= u & -u) if (ans.first < bit[u].first) ans = bit[u];
else if (ans.first == bit[u].first) add(ans.second, bit[u].second);
return ans;
}
};
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n;
vector <int> ctz;
FOR(i, 0, n) {
if (i > 0) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
ctz.push_back(a[i].a);
ctz.push_back(a[i].b);
ctz.push_back(a[i].c);
ctz.push_back(a[i].d);
}
sort (ALL(ctz));
ctz.erase(unique(ALL(ctz)), ctz.end());
FOR(i, 1, n) {
a[i].a = lower_bound(ALL(ctz), a[i].a) - ctz.begin() + 1;
a[i].b = lower_bound(ALL(ctz), a[i].b) - ctz.begin() + 1;
a[i].c = lower_bound(ALL(ctz), a[i].c) - ctz.begin() + 1;
a[i].d = lower_bound(ALL(ctz), a[i].d) - ctz.begin() + 1;
line.push_back(LINE(a[i].a, a[i].c, i, 1));
line.push_back(LINE(a[i].b, a[i].d, i, -1));
}
//FOR(i, 1, n) {
// cout << a[i].a << ' ' << a[i].b << ' ' << a[i].c << ' ' << a[i].d << '\n';
//}
sort (ALL(line));
Fenwick_Tree mybit(4e6);
mybit.update(lower_bound(ALL(ctz), 0) - ctz.begin() + 1, make_pair(0, 1));
for (auto x : line) {
if (x.type == -1) {
mybit.update(a[x.id].d, res[x.id]);
}
else {
res[x.id] = mybit.get(a[x.id].c);
res[x.id].first++;
}
}
pair <int, int> ans = make_pair(0, 1);
FOR(i, 1, n) if (ans.first < res[i].first) {
ans = res[i];
}
else if (ans.first == res[i].first) add(ans.second, res[i].second);
cout << ans.first << ' ' << ans.second << '\n';
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
trapezoid.cpp: In function 'void file()':
trapezoid.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
12 ms |
31560 KB |
Output is correct |
| 3 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
14 ms |
31708 KB |
Output is correct |
| 5 |
Correct |
15 ms |
31828 KB |
Output is correct |
| 6 |
Correct |
15 ms |
32012 KB |
Output is correct |
| 7 |
Correct |
18 ms |
32168 KB |
Output is correct |
| 8 |
Correct |
18 ms |
32208 KB |
Output is correct |
| 9 |
Correct |
25 ms |
32704 KB |
Output is correct |
| 10 |
Correct |
34 ms |
33612 KB |
Output is correct |
| 11 |
Correct |
43 ms |
34180 KB |
Output is correct |
| 12 |
Correct |
72 ms |
36544 KB |
Output is correct |
| 13 |
Correct |
88 ms |
37480 KB |
Output is correct |
| 14 |
Correct |
102 ms |
38592 KB |
Output is correct |
| 15 |
Correct |
110 ms |
39076 KB |
Output is correct |
| 16 |
Correct |
118 ms |
39532 KB |
Output is correct |
| 17 |
Correct |
123 ms |
40032 KB |
Output is correct |
| 18 |
Correct |
114 ms |
40548 KB |
Output is correct |
| 19 |
Correct |
128 ms |
41172 KB |
Output is correct |
| 20 |
Correct |
140 ms |
41508 KB |
Output is correct |
