#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define pb push_back
#define fi first
#define se second
using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;
const int MAXN = 1e5 + 5;
int n, N;
array<int, 4> points[MAXN];
set<vector<int>> events;
set<int> num;
map<int, int> compress;
pii seg[MAXN * 16];
pii smaller[MAXN];
const ll mod = 30013;
pii comp(pii a, pii b){
if(a.fi == b.fi) return {a.fi, (a.se + b.se) % mod};
if(a.fi > b.fi) return a;
return b;
}
void insert(int i, int l, int r, int pos, pii val){
if(l == r){
seg[i] = comp(seg[i], val);
return;
}
int mid = (l + r) / 2;
if(pos <= mid) insert(i * 2, l, mid, pos, val);
else insert(i * 2 + 1, mid + 1, r, pos, val);
seg[i] = comp(seg[i * 2], seg[i * 2 + 1]);
}
pii query(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r) return {0, 0};
if(ql <= l && r <= qr) return seg[i];
int mid = (l + r) / 2;
if(qr <= mid) return query(i * 2, l, mid, ql, qr);
if(ql > mid) return query(i * 2 + 1, mid + 1, r, ql, qr);
return comp(query(i * 2, l, mid, ql, qr), query(i * 2 + 1, mid + 1, r, ql, qr));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
rep(i, 0, n){
int a, b, c, d;
cin >> a >> b >> c >> d;
points[i] = {a, b, c, d};
events.insert({a, 1, i});
events.insert({b, 2, i});
num.insert(a);
num.insert(b);
num.insert(c);
num.insert(d);
}
int cnt = 1;
for(auto x : num)
compress[x] = cnt++;
N = 1;
while(N < cnt) N *= 2;
insert(1, 0, N - 1, 0, {0, 1});
for(auto event : events){
int type = event[1];
int i = event[2];
auto [a, b, c, d] = points[i];
a = compress[a];
b = compress[b];
c = compress[c];
d = compress[d];
if(type == 1){
smaller[i] = query(1, 0, N - 1, 0, c - 1);
smaller[i].fi += 1;
} else {
insert(1, 0, N - 1, d, smaller[i]);
}
}
pii res = query(1, 0, N - 1, 0, N - 1);
cout << res.fi << " " << res.se << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |