#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
// using namespace __gnu_pbds;
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}
#define epl emplace
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define lwb lower_bound
#define upb upper_bound
#define ctz __builtin_ctzll // or __builtin_ctz
#define pct __builtin_popcountll // or __builtin_popcount
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}
// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 1e5 + 3, MOD = 30013;
void add(int &a, int b){
a += b; if(a >= MOD) a -= MOD;
}
int sum(const int a, const int b){
int res = a + b;
if(res >= MOD) res -= MOD;
return res;
}
struct point{
int x, y, id, type;
bool operator < (const point &oth) const{
return x == oth.x ? type < oth.type : x < oth.x;
}
} p[N << 1];
int n;
pii dp[N], ans, st[N << 2];
void update(int id, int L, int R, int p, pii v){
if(L == R){
if(st[id].fi < v.fi) st[id] = v;
else if(st[id].fi == v.fi) add(st[id].se, v.se);
return;
}
int mid = L + R >> 1;
if(p <= mid) update(id << 1, L, mid, p, v);
else update(id << 1 | 1, mid + 1, R, p, v);
if(st[id << 1].fi != st[id << 1 | 1].fi) st[id] = max(st[id << 1], st[id << 1 | 1]);
else st[id] = {st[id << 1].fi, sum(st[id << 1].se, st[id << 1 | 1].se)};
}
pii get_ans(int id, int L, int R, int Lq, int Rq){
if(R < Lq || Rq < L) return mp(0, 0);
if(Lq <= L && R <= Rq) return st[id];
int mid = L + R >> 1;
pii ret1 = get_ans(id << 1, L, mid, Lq, Rq);
pii ret2 = get_ans(id << 1 | 1, mid + 1, R, Lq, Rq);
if(ret1.fi != ret2.fi) return max(ret1, ret2);
return mp(ret1.fi, sum(ret1.se, ret2.se));
}
void TS_2392(){
cin >> n;
vector<int> tmpx, tmpy;
for(int i = 1; i <= n; ++i){
cin >> p[i].x >> p[i + n].x >> p[i].y >> p[i + n].y;
p[i].id = p[i + n].id = i; p[i].type = 0; p[i + n].type = 1;
tmpx.eb(p[i].x); tmpx.eb(p[i + n].x);
tmpy.eb(p[i].y); tmpy.eb(p[i + n].y);
}
ans = {0, 1};
remDup(tmpx); remDup(tmpy);
for(int i = 1; i <= 2 * n; ++i){
p[i].x = lwb(all(tmpx), p[i].x) - tmpx.begin() + 1;
p[i].y = lwb(all(tmpy), p[i].y) - tmpy.begin() + 1;
}
sort(p + 1, p + 1 + 2 * n);
for(int i = 1; i <= 2 * n; ++i){
int id = p[i].id;
if(p[i].type == 0){
dp[id] = get_ans(1, 1, 2 * n, 1, p[i].y - 1);
if(dp[id].fi == 0) dp[id] = {1, 1};
else ++dp[id].fi;
if(ans.fi < dp[id].fi) ans = dp[id];
else if(ans.fi == dp[id].fi) add(ans.se, dp[id].se);
}
else{
update(1, 1, 2 * n, p[i].y, dp[id]);
}
}
cout << ans.fi << ' ' << ans.se;
}
int main(){
SPEED; fileIO("textA");
int num_test = 1; //cin >> num_test;
for(int itest = 1; itest <= num_test; ++itest){
TS_2392();
}
return 0;
}
Compilation message
trapezoid.cpp: In function 'void update(int, int, int, int, pii)':
trapezoid.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid = L + R >> 1;
| ~~^~~
trapezoid.cpp: In function 'pii get_ans(int, int, int, int, int)':
trapezoid.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = L + R >> 1;
| ~~^~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:124:12: note: in expansion of macro 'fileIO'
124 | SPEED; fileIO("textA");
| ^~~~~~
trapezoid.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:124:12: note: in expansion of macro 'fileIO'
124 | SPEED; fileIO("textA");
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2904 KB |
Output is correct |
| 9 |
Correct |
11 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
22 ms |
6572 KB |
Output is correct |
| 11 |
Correct |
28 ms |
6616 KB |
Output is correct |
| 12 |
Correct |
63 ms |
8768 KB |
Output is correct |
| 13 |
Correct |
72 ms |
9160 KB |
Output is correct |
| 14 |
Incorrect |
87 ms |
9904 KB |
Output isn't correct |
| 15 |
Incorrect |
99 ms |
9920 KB |
Output isn't correct |
| 16 |
Incorrect |
104 ms |
10304 KB |
Output isn't correct |
| 17 |
Incorrect |
105 ms |
10732 KB |
Output isn't correct |
| 18 |
Incorrect |
100 ms |
10944 KB |
Output isn't correct |
| 19 |
Incorrect |
112 ms |
11196 KB |
Output isn't correct |
| 20 |
Incorrect |
123 ms |
11712 KB |
Output isn't correct |
