#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;
}
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 && ok == a.ok) return idx < a.idx;
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> cpx , cpy;
void solve()
{
cin >> n;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i].x >> a[i].u >> a[i].y >> a[i].v;
cpx.pb(a[i].x);
cpy.pb(a[i].y);
cpx.pb(a[i].u);
cpy.pb(a[i].v);
}
sort(all(cpx));
cpx.erase(unique(all(cpx)) , cpx.end());
sort(all(cpy));
cpy.erase(unique(all(cpy)) , cpy.end());
for(int i = 1 ; i <= n ; i++) {
a[i].x = lower_bound(all(cpx) , a[i].x) - cpx.begin() + 1;
a[i].y = lower_bound(all(cpy) , a[i].y) - cpy.begin() + 1;
a[i].u = lower_bound(all(cpx) , a[i].u) - cpx.begin() + 1;
a[i].v = lower_bound(all(cpy) , a[i].v) - cpy.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(int i = 1 ; i <= n ; i++) {
if(a[i].x > a[i].u || a[i].y > a[i].v) {
cout << -1;
exit(0);
}
}
for(auto it : val)
{
int i = it.idx;
if(it.ok == 0) {
//cout << it.r << ' ' << f[i] << ' ' << g[i] << endl;
if(f[i] == 0) {
cout << -1;
exit(0);
}
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:71:1: warning: no return statement in function returning non-void [-Wreturn-type]
71 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
3 ms |
588 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
3 ms |
716 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
4 ms |
844 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
7 ms |
960 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
6 ms |
1100 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
8 ms |
1176 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
12 ms |
1488 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
22 ms |
2340 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
27 ms |
2736 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
55 ms |
4020 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
68 ms |
4988 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
101 ms |
6696 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
90 ms |
6848 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
91 ms |
7008 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
93 ms |
7184 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
97 ms |
7332 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
116 ms |
7564 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
112 ms |
7640 KB |
Execution killed with signal 11 |
