#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod = 30013;
struct fentree{
struct node{
int v=0, cnt=0;
node operator+(node b){
if (b.v==v) return {v,(cnt+b.cnt)%mod};
else if (b.v<v) return {v,cnt};
else return b;
}
};
int n;
vector<node> a;
fentree( int N ) : n(N), a(N+1) {}
auto get(int r){
node ans = {0,0};
for(r++; r>0; r-=r&(-r)) ans = ans + a[r];
return ans;
}
void update(int at, int v, int ways){
node u = {v,ways};
for(at++; at<n; at+=at&(-at)) a[at] = a[at] + u;
}
};
const int oo = ll(2e9);
int main(){
cin.tie(NULL),cin.sync_with_stdio(false);
int n; cin >> n;
vector<array<int,4>> a(n+1);
vi coords;
rep(i,0,n){
rep(j,0,4) cin >> a[i][j];
rep(j,0,4) coords.push_back(a[i][j]);
}
coords.push_back(oo);
a[n] = {oo,oo,oo,oo};
sort(all(coords));
coords.erase(unique(all(coords)),end(coords));
auto ctoi = [&coords](int at) -> int {
return lower_bound(all(coords),at)-begin(coords);
};
for(auto& v : a) rep(i,0,4) v[i] = ctoi(v[i]);
int m = sz(coords);
priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;
fentree fen(m);
fen.update(0,0,1);
sort(all(a));
for(auto [a1,a2,b1,b2] : a){
while (sz(pq) and pq.top()[0]<=a1){
auto [x,y,v,w] = pq.top();
pq.pop();
fen.update(y,v,w);
}
auto ret = fen.get(b1);
pq.push({a2,b2,ret.v+1,ret.cnt});
}
assert(sz(pq) == 1);
cout << pq.top()[2]-1 << ' ' << pq.top()[3] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
608 KB |
Output is correct |
7 |
Correct |
4 ms |
604 KB |
Output is correct |
8 |
Correct |
5 ms |
860 KB |
Output is correct |
9 |
Correct |
10 ms |
1248 KB |
Output is correct |
10 |
Correct |
17 ms |
2084 KB |
Output is correct |
11 |
Correct |
23 ms |
2564 KB |
Output is correct |
12 |
Correct |
48 ms |
4812 KB |
Output is correct |
13 |
Correct |
65 ms |
5584 KB |
Output is correct |
14 |
Partially correct |
76 ms |
6724 KB |
Partially correct |
15 |
Correct |
87 ms |
6692 KB |
Output is correct |
16 |
Correct |
84 ms |
7368 KB |
Output is correct |
17 |
Correct |
93 ms |
8136 KB |
Output is correct |
18 |
Correct |
81 ms |
7100 KB |
Output is correct |
19 |
Partially correct |
95 ms |
8648 KB |
Partially correct |
20 |
Correct |
110 ms |
8996 KB |
Output is correct |