#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int a[100005], b[100005], c[100005], d[100005];
int dp[100005];
int num[100005], cnt[100005], pcnt[100005];
int rcnt[100005];
struct seg{int a,b,p,i;}st[100005];
bool cmp(seg a, seg b){return a.a < b.a;}
struct seg2{int dp,a,b,p,i,num;}st2[100005];
bool cmp2(seg2 a, seg2 b){return a.b < b.b;}
bool cmp3(seg2 a, seg2 b){return a.a < b.a;}
struct rmq{
int lim, *tree;
void init(int n){
for(lim = 1; lim <= n; lim <<= 1);
tree = (int*) calloc(2*lim+1, sizeof(int));
}
void ins(int s, int v){
s += lim;
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 idx{
int lim, *tree;
void init(int n){
for(lim = 1; lim <= n; lim <<= 1);
tree = (int*) calloc(2*lim+1, sizeof(int));
}
void ins(int s, int v){
s += lim;
tree[s] = v;
while(s>1){
s >>= 1;
tree[s] = tree[2*s] + tree[2*s+1];
tree[s] %= 30013;
}
}
int q(int s, int e){
s += lim;
e += lim;
int r = 0;
while(s<e){
if(s%2 == 1) r += tree[s++];
if(e%2 == 0) r += tree[e--];
s >>= 1;
e >>= 1;
}
if(s == e) r += tree[s];
return r % 30013;
}
}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);
}
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,-1};
}
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,-1};
}
}
int mcnt = *max_element(dp,dp+n);
printf("%d ",mcnt);
for (int i=0; i<n; i++) {
cnt[dp[i]]++;
}
for (int i=1; i<=n; i++) {
cnt[i] += cnt[i-1];
}
sort(st2,st2+2*n,cmp2);
for (int i=0; i<2*n; i++) {
if(st2[i].p == 0){
num[st2[i].i] = st2[i].num = cnt[dp[st2[i].i] - 1] + (pcnt[dp[st2[i].i]]++);
}
else{
st2[i].num = num[st2[i].i];
}
}
sort(st2,st2+2*n,cmp3);
idx.init(n);
for (int i=0; i<2*n; i++) {
if(st2[i].p == 0){
if(st2[i].dp == 1) rcnt[st2[i].i] = 1;
else rcnt[st2[i].i] = idx.q(cnt[st2[i].dp-2], cnt[st2[i].dp-1]-1);
}
else{
idx.ins(st2[i].num,rcnt[st2[i].i]);
}
}
int acnt = 0;
for (int i=0; i<n; i++) {
if(dp[i] == mcnt){
acnt += rcnt[i];
acnt %= 30013;
}
}
printf("%d",acnt);
}
Compilation message
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:96:33: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st[2*i] = {a[i],c[i],0,i};
^
trapezoid.cpp:96:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st[2*i] = {a[i],c[i],0,i};
^
trapezoid.cpp:97:35: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st[2*i+1] = {b[i],d[i],1,i};
^
trapezoid.cpp:97:19: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st[2*i+1] = {b[i],d[i],1,i};
^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:107:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
^
trapezoid.cpp:107:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st2[i] = {dp[st[i].i],st[i].a,st[i].b,0,st[i].i,-1};
^
trapezoid.cpp:111:63: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
^
trapezoid.cpp:111:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
st2[i] = {dp[st[i].i],st[i].a,st[i].b,1,st[i].i,-1};
^
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:80:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
trapezoid.cpp:83:53: 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 |
0 ms |
8600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8600 KB |
Output is correct |
| 3 |
Partially correct |
0 ms |
8600 KB |
Partially correct |
| 4 |
Correct |
0 ms |
8600 KB |
Output is correct |
| 5 |
Partially correct |
3 ms |
8744 KB |
Partially correct |
| 6 |
Partially correct |
6 ms |
8740 KB |
Partially correct |
| 7 |
Correct |
6 ms |
8740 KB |
Output is correct |
| 8 |
Partially correct |
9 ms |
8892 KB |
Partially correct |
| 9 |
Partially correct |
19 ms |
9152 KB |
Partially correct |
| 10 |
Correct |
36 ms |
9796 KB |
Output is correct |
| 11 |
Partially correct |
53 ms |
9796 KB |
Partially correct |
| 12 |
Partially correct |
109 ms |
11080 KB |
Partially correct |
| 13 |
Partially correct |
143 ms |
11080 KB |
Partially correct |
| 14 |
Runtime error |
179 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
189 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
219 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
199 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
186 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
216 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
226 ms |
13384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
