#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 2e5 + 227;
const int inf = 1e9 + 277;
const int mod = 30013;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l , ll r) {
return l + rd() * 1LL * rd() % (r - l + 1);
}
struct item {
int x, y, u, v;
} a[mxN];
struct SEG
{
int l, r, ok , idx;
bool operator<(const SEG &a) const
{
return l < a.l;
}
};
int n;
int f[mxN];
int g[mxN];
void add(int &a , int b)
{
a += b;
if(a >= mod) a -= mod;
}
pair<int , int> bitmax[mxN * 4];
void updatemax(int pos, int val1 , int val2)
{
for(; pos <= n * 4 ; pos += pos & -pos) {
if(maximize(bitmax[pos].fi , val1) == true) bitmax[pos].se = val2;
else if(bitmax[pos].fi == val1) add(bitmax[pos].se , val2);
}
}
pair<int , int> getmax(int pos)
{
pair<int , int> res = {-1 , -1};
for(; pos > 0 ; pos -= pos & -pos) {
if(maximize(res.fi , bitmax[pos].fi) == true) res.se = bitmax[pos].se;
else if(res.fi == bitmax[pos].fi) add(res.se , bitmax[pos].se);
}
return res;
}
vector<int> cp;
bool vis[mxN];
void solve()
{
// n = Rand(2 , 3);
cin >> n;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
// a[i].x = Rand(1 , 10);
// a[i].y = Rand(1 , 10);
// a[i].u = Rand(a[i].x , 20);
// a[i].v = Rand(a[i].y , 20);
cp.pb(a[i].x);
cp.pb(a[i].y);
cp.pb(a[i].u);
cp.pb(a[i].v);
}
//cout << n << endl;
//for(int i = 1 ; i <= n ; i++)
// cout << a[i].x << ' ' << a[i].u << ' ' << a[i].y << ' ' << a[i].v << endl;
sort(all(cp));
cp.erase(unique(all(cp)) , cp.end());
for(int i = 1 ; i <= n ; i++) {
a[i].x = lower_bound(all(cp) , a[i].x) - cp.begin() + 1;
a[i].y = lower_bound(all(cp) , a[i].y) - cp.begin() + 1;
a[i].u = lower_bound(all(cp) , a[i].u) - cp.begin() + 1;
a[i].v = lower_bound(all(cp) , a[i].v) - cp.begin() + 1;
}
vector<SEG> val;
for(int i = 1 ; i <= n ; i++)
{
int x = a[i].x;
int y = a[i].y;
int u = a[i].u;
int v = a[i].v;
val.pb({x , y , 1 , i});
//cout << val.back().idx << endl;
val.pb({u , v , 0 , i});
//cout << val.back().idx << endl;
}
sort(all(val));
// for(int i = 0 ; i < sz(val) ; i++) {
// auto it = val[i];
// if(it.ok == 0) {
// if(vis[it.idx] == false) {
// cout << it.l << ' ' << it.r << ' ' << it.ok << ' ' << it.idx << endl;
// cout << a[it.idx].x << ' ' << a[it.idx].y << ' ' << a[it.idx].u << ' ' << a[it.idx].v << endl;
// cout << "f";
// exit(0);
// }
// }
// else {
// vis[it.idx] = true;
// }
// }
g[0] = 1;
for(auto it : val)
{
int i = it.idx;
if(it.ok == 0) {
//cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
updatemax(it.r , f[i] , g[i]);
}
else {
f[i] = max(1 , getmax(it.r - 1).fi + 1);
if(f[i] == 1) g[i] = 1;
else g[i] = getmax(it.r - 1).se;
}
}
int res = getmax(4 * n).fi;
int ans = getmax(4 * n).se;
cout << res << ' ' << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp" , "r" , stdin);
//freopen(TASK".out" , "w" , stdout);
int tc = 1;
//cin >> tc;
while(tc--)
{
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
588 KB |
Output is correct |
| 6 |
Correct |
4 ms |
716 KB |
Output is correct |
| 7 |
Correct |
4 ms |
716 KB |
Output is correct |
| 8 |
Correct |
6 ms |
884 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1308 KB |
Output is correct |
| 10 |
Correct |
22 ms |
2140 KB |
Output is correct |
| 11 |
Correct |
28 ms |
2884 KB |
Output is correct |
| 12 |
Correct |
59 ms |
4988 KB |
Output is correct |
| 13 |
Correct |
88 ms |
6296 KB |
Output is correct |
| 14 |
Correct |
85 ms |
7368 KB |
Output is correct |
| 15 |
Correct |
96 ms |
7292 KB |
Output is correct |
| 16 |
Correct |
103 ms |
8000 KB |
Output is correct |
| 17 |
Correct |
105 ms |
8756 KB |
Output is correct |
| 18 |
Correct |
95 ms |
8120 KB |
Output is correct |
| 19 |
Correct |
111 ms |
9296 KB |
Output is correct |
| 20 |
Correct |
127 ms |
9876 KB |
Output is correct |
