#include <bits/stdc++.h>
#include <cmath>
using namespace std;
struct Segment {
long long ways,num;
};
const int mod = 30013;
Segment join(Segment A, Segment B) {
Segment ret;
if (A.num > B.num) return A;
if (B.num > A.num) return B;
ret.num = A.num;
ret.ways = (A.ways+B.ways)%mod;
return ret;
}
Segment id;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = id; T comb(T a, T b) { return join(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
// keep track of min trap that intersects with curr trap
Seg<Segment> lis;
struct Trapezoid {
int a,b,c,d;
const bool operator<(const Trapezoid& o) const {
if(b < o.a & d < o.c) return 1;
return a < o.a;
}
};
vector<Trapezoid> traps;
bool intersect(int i, int j) {
return (traps[i].b > traps[j].a || traps[i].d > traps[j].c);
}
int main() {
int n; cin >> n;
Trapezoid t;
for(int i = 0; i < n; i++) {
cin >> t.a >> t.b >> t.c >> t.d;
traps.push_back(t);
}
lis.init(n+1);
sort(begin(traps),end(traps));
Segment f;
f.num = 1;
f.ways = 1;
lis.upd(1,f);
int ind = 0;
Segment ret;
ret.num = 1;
ret.ways = 1;
Segment res;
for(int i = 1; i < n; i++) {
while (ind != i && !intersect(ind,i)) ind++;
res = lis.query(1,ind);
res.num++;
if (res.ways == 0) res.ways = 1;
ret = join(ret,res);
lis.upd(i+1,res);
}
cout << ret.num << " " << ret.ways << endl;
}
Compilation message
trapezoid.cpp: In member function 'const bool Trapezoid::operator<(const Trapezoid&) const':
trapezoid.cpp:48:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
48 | if(b < o.a & d < o.c) return 1;
| ~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
460 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
648 KB |
Output isn't correct |
| 9 |
Incorrect |
12 ms |
904 KB |
Output isn't correct |
| 10 |
Incorrect |
26 ms |
1252 KB |
Output isn't correct |
| 11 |
Incorrect |
31 ms |
1468 KB |
Output isn't correct |
| 12 |
Incorrect |
65 ms |
2740 KB |
Output isn't correct |
| 13 |
Incorrect |
86 ms |
3260 KB |
Output isn't correct |
| 14 |
Incorrect |
94 ms |
3636 KB |
Output isn't correct |
| 15 |
Incorrect |
95 ms |
3824 KB |
Output isn't correct |
| 16 |
Incorrect |
102 ms |
4148 KB |
Output isn't correct |
| 17 |
Incorrect |
116 ms |
4388 KB |
Output isn't correct |
| 18 |
Incorrect |
124 ms |
4644 KB |
Output isn't correct |
| 19 |
Incorrect |
122 ms |
4868 KB |
Output isn't correct |
| 20 |
Incorrect |
127 ms |
5028 KB |
Output isn't correct |
