#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define fi first
#define se second
typedef pair<int, int> ii;
int md = 30013;
struct fw{
int n;
vector<ii> bit;
fw(int siz){
n = siz;
bit.resize(n + 1, {0, 0});
}
void ud(int pos, ii val){
while (pos <= n){
if (val.fi > bit[pos].fi) bit[pos].se = val.se;
else if (val.fi == bit[pos].fi) bit[pos].se = (bit[pos].se + val.se) % md;
bit[pos].fi = max(bit[pos].fi, val.fi);
pos += (pos & (-pos));
}
}
ii get(int pos){
ii rt = {0, 1};
while (pos >= 1){
if (bit[pos].fi == rt.fi) rt.se = (rt.se + bit[pos].se) % md;
else if (rt.fi < bit[pos].fi) rt.se = bit[pos].se;
rt.fi = max(rt.fi, bit[pos].fi);
pos -= (pos & (-pos));
}
return rt;
}
};
struct iii{
int l, r, typ, idx;
bool operator < (iii& o){
return l < o.l;
}
};
int n;
ii res[N];
vector<iii> vec;
vector<int> cy;
map<int, int> dd;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++){
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
cy.push_back(l2);
cy.push_back(r2);
vec.push_back({l1, l2, 0, i});
vec.push_back({r1, r2, 1, i});
}
sort(cy.begin(), cy.end());
cy.resize(unique(cy.begin(), cy.end()) - cy.begin());
sort(vec.begin(), vec.end());
int pos = 0;
for (auto x : cy) dd[x] = ++pos;
fw s1(pos);
for (auto x : vec){
int pos = dd[x.r];
if (x.typ == 0){
ii dp = s1.get(pos);
dp.fi++;
res[x.idx] = dp;
//cout << " check1 :" << x.idx << " " << dp.fi << " " << dp.se << " " << pos << " " << x.l<< "\n";
continue;
}
// cout << " check2 : " << x.idx << " " << pos << " " << res[x.idx].fi << " "<< res[x.idx].se << " " << x.l << "\n";
s1.ud(pos, res[x.idx]);
}
ii ans = s1.get((int) cy.size());
cout << ans.fi << " " << ans.se;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
3 ms |
1116 KB |
Output is correct |
8 |
Correct |
5 ms |
1372 KB |
Output is correct |
9 |
Correct |
10 ms |
2136 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
24 ms |
4840 KB |
Output is correct |
12 |
Correct |
56 ms |
9540 KB |
Output is correct |
13 |
Correct |
67 ms |
11336 KB |
Output is correct |
14 |
Correct |
83 ms |
13368 KB |
Output is correct |
15 |
Correct |
87 ms |
14136 KB |
Output is correct |
16 |
Correct |
96 ms |
15016 KB |
Output is correct |
17 |
Correct |
100 ms |
15932 KB |
Output is correct |
18 |
Correct |
84 ms |
16956 KB |
Output is correct |
19 |
Correct |
110 ms |
17668 KB |
Output is correct |
20 |
Correct |
119 ms |
18744 KB |
Output is correct |