#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int mod = 30013;
int n;
int a[100005], b[100005], c[100005], d[100005];
int dp[100005], cnt[100005];
struct seg{int a,b,p,i;}st[200005];
bool cmp(seg a, seg b){return make_tuple(a.a, a.b, a.p) < make_tuple(b.a, b.b, b.p); }
struct seg2{int dp,a,b,p,i;}st2[200005];
bool cmp2(seg2 a, seg2 b){return make_tuple(a.a, a.b, a.p) < make_tuple(b.a, b.b, b.p); }
struct rmq{
int lim, tree[530000];
void init(int n){
for(lim = 1; lim <= n; lim <<= 1);
}
void ins(int s, int v){
s += lim;
tree[s] = max(tree[s], v);
while(s>1){
s >>= 1;
tree[s] = max(tree[2*s],tree[2*s+1]);
}
}
int q(int s, int e){
s += lim;
e += lim;
int r = 0;
while(s<e){
if(s%2 == 1) r = max(r,tree[s++]);
if(e%2 == 0) r = max(r,tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) r = max(r,tree[s]);
return r;
}
}rmq;
struct bit{
int lim, tree[132000];
void init(int n){
n += 2;
for(lim = 1; lim <= n; lim <<= 1);
}
void add(int x, int v){
x += 2;
while(x <= lim){
tree[x] += v;
tree[x] %= mod;
x += x & -x;
}
}
int sum(int x){
x += 2;
int r = 0;
while(x){
r += tree[x];
r %= mod;
x -= x & -x;
}
return r;
}
}idx;
void input(){
vector<int> vu, vd;
scanf("%d",&n);
rmq.init(2*n);
for (int i=0; i<n; i++) {
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
vu.push_back(a[i]);
vu.push_back(b[i]);
vd.push_back(c[i]);
vd.push_back(d[i]);
}
sort(vu.begin(),vu.end());
sort(vd.begin(),vd.end());
for (int i=0; i<n; i++) {
a[i] = (int)(lower_bound(vu.begin(),vu.end(),a[i]) - vu.begin());
b[i] = (int)(lower_bound(vu.begin(),vu.end(),b[i]) - vu.begin());
c[i] = (int)(lower_bound(vd.begin(),vd.end(),c[i]) - vd.begin());
d[i] = (int)(lower_bound(vd.begin(),vd.end(),d[i]) - vd.begin());
st[2*i] = {a[i],c[i],0,i};
st[2*i+1] = {b[i],d[i],1,i};
}
sort(st,st+2*n,cmp);
}
vector<pi> v;
int main(){
input();
for (int i=0; i<2*n; i++) {
if(st[i].p == 0){
dp[st[i].i] = rmq.q(0,st[i].b) + 1;
st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i};
}
else{
rmq.ins(st[i].b,dp[st[i].i]);
st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i};
}
}
int mcnt = *max_element(dp,dp+n);
printf("%d ",mcnt);
for (int i=0; i<2*n; i++) {
if(st2[i].p == 1) v.push_back(pi(st2[i].dp,st2[i].b));
}
sort(v.begin(),v.end());
sort(st2,st2+2*n,cmp2);
idx.init(n);
int acnt = 0;
for (int i=0; i<2*n; i++) {
if(st2[i].p == 0){
if(st2[i].dp == 1){
cnt[st2[i].i] = 1;
}
else{
int start = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp-1,0)) - v.begin());
int end = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp-1,st2[i].b)) - v.begin());
cnt[st2[i].i] = idx.sum(end-1) - idx.sum(start-1);
if(st2[i].dp == mcnt) acnt += cnt[st2[i].i];
}
}
else{
int pos = (int)(lower_bound(v.begin(),v.end(),pi(st2[i].dp,st2[i].b)) - v.begin());
idx.add(pos,cnt[st2[i].i]);
}
acnt %= mod;
}
if(acnt < 0) acnt += mod;
printf("%d",acnt);
}
Compilation message
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
trapezoid.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
504 KB |
Output is correct |
| 4 |
Correct |
7 ms |
504 KB |
Output is correct |
| 5 |
Correct |
9 ms |
760 KB |
Output is correct |
| 6 |
Correct |
11 ms |
888 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1224 KB |
Output is correct |
| 9 |
Correct |
26 ms |
1996 KB |
Output is correct |
| 10 |
Correct |
44 ms |
3620 KB |
Output is correct |
| 11 |
Correct |
58 ms |
4316 KB |
Output is correct |
| 12 |
Correct |
116 ms |
8396 KB |
Output is correct |
| 13 |
Correct |
137 ms |
9772 KB |
Output is correct |
| 14 |
Correct |
165 ms |
12020 KB |
Output is correct |
| 15 |
Correct |
187 ms |
12540 KB |
Output is correct |
| 16 |
Correct |
201 ms |
13264 KB |
Output is correct |
| 17 |
Correct |
216 ms |
14108 KB |
Output is correct |
| 18 |
Correct |
198 ms |
14800 KB |
Output is correct |
| 19 |
Correct |
221 ms |
15492 KB |
Output is correct |
| 20 |
Correct |
245 ms |
16180 KB |
Output is correct |
