#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;
vector<pair<pair<int,int>,pair<int,int>>> traps;
bool intersect(int i, int j) {
return (traps[i].second.first > traps[j].first.first || traps[i].second.second > traps[j].first.second);
}
int main() {
int n; cin >> n;
int a,b,c,d;
for(int i = 0; i < n; i++) {
cin >> a >> b >> c >> d;
traps.push_back({{a,c},{b,d}});
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
300 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 6 |
Incorrect |
6 ms |
460 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
588 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
716 KB |
Output isn't correct |
| 9 |
Incorrect |
12 ms |
1096 KB |
Output isn't correct |
| 10 |
Incorrect |
26 ms |
1804 KB |
Output isn't correct |
| 11 |
Incorrect |
31 ms |
2252 KB |
Output isn't correct |
| 12 |
Incorrect |
64 ms |
4032 KB |
Output isn't correct |
| 13 |
Incorrect |
77 ms |
4760 KB |
Output isn't correct |
| 14 |
Incorrect |
92 ms |
5624 KB |
Output isn't correct |
| 15 |
Incorrect |
99 ms |
5808 KB |
Output isn't correct |
| 16 |
Incorrect |
106 ms |
6308 KB |
Output isn't correct |
| 17 |
Incorrect |
110 ms |
6692 KB |
Output isn't correct |
| 18 |
Incorrect |
112 ms |
6944 KB |
Output isn't correct |
| 19 |
Incorrect |
124 ms |
7452 KB |
Output isn't correct |
| 20 |
Incorrect |
131 ms |
7944 KB |
Output isn't correct |
