#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 = 1e5 + 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<(seg a)
{
if(l == a.l && r == a.r) return ok > a.ok;
if(l == a.l) return r < a.r;
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;
}
int bitadd[mxN * 2];
void updateadd(int pos, int val)
{
for(; pos <= 2 * n ; pos += pos & -pos) add(bitadd[pos] , val);
}
int getsum(int pos)
{
int res = 0;
for(; pos > 0 ; pos -= pos & -pos) add(res , bitadd[pos]);
return res;
}
int getsum(int l , int r)
{
int res = getsum(r) - getsum(l - 1);
if(res < 0) res += mod;
}
int bitmax[mxN * 2];
void updatemax(int pos, int val)
{
for(; pos <= n * 2 ; pos += pos & -pos) maximize(bitmax[pos] , val);
}
int getmax(int pos)
{
int res = 0;
for(; pos > 0 ; pos -= pos & -pos) maximize(res , bitmax[pos]);
return res;
}
vector<int> valx , valy;
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);
valx.pb(a[i].x);
valy.pb(a[i].y);
valx.pb(a[i].u);
valy.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(valx));
valx.erase(unique(all(valx)) , valx.end());
sort(all(valy));
valy.erase(unique(all(valy)) , valy.end());
for(int i = 1 ; i <= n ; i++) {
a[i].x = lower_bound(all(valx) , a[i].x) - valx.begin() + 1;
a[i].y = lower_bound(all(valy) , a[i].y) - valy.begin() + 1;
a[i].u = lower_bound(all(valx) , a[i].u) - valx.begin() + 1;
a[i].v = lower_bound(all(valy) , a[i].v) - valy.begin() + 1;
}
vector<seg> val;
for(int i = 1 ; i <= n ; i++)
{
val.pb({a[i].x , a[i].y , 1 , i});
val.pb({a[i].u , a[i].v , 0 , i});
}
sort(all(val));
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]);
updateadd(f[i] , g[i]);
}
else {
f[i] = max(1 , getmax(it.r - 1) + 1);
if(f[i] == 1) g[i] = 1;
else g[i] = getsum(f[i] - 1 , f[i] - 1);
}
}
int res = getmax(2 * n);
int ans = getsum(res , res);
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;
}
Compilation message
trapezoid.cpp: In function 'int getsum(int, int)':
trapezoid.cpp:77:1: warning: no return statement in function returning non-void [-Wreturn-type]
77 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
3 ms |
588 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
5 ms |
588 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
3 ms |
716 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
6 ms |
844 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
6 ms |
996 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
6 ms |
992 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
9 ms |
1192 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
12 ms |
1620 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
22 ms |
2380 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
27 ms |
2756 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
63 ms |
4036 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
73 ms |
4712 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
81 ms |
6704 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
86 ms |
6856 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
94 ms |
7016 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
95 ms |
7176 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
100 ms |
7412 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
107 ms |
7476 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
122 ms |
7644 KB |
Execution killed with signal 11 |
