#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mod 30013
#define maxn 200010
struct node {
int a,b,c,d;
};
int n,szx,szy;
pii val[maxn];
pii tree[maxn];
node p[maxn];
vector<int> ass[maxn];
vector<int> hole[maxn];
map<int,int> mpx;
map<int,int> mpy;
void cpidx() {
int i;
map<int,int>::iterator it;
for(i=1;i<=n;i++) mpx[p[i].a], mpx[p[i].b];
for(i=1;i<=n;i++) mpy[p[i].c], mpy[p[i].d];
for(it=mpx.begin();it!=mpx.end();++it) it->second = ++szx;
for(it=mpy.begin();it!=mpy.end();++it) it->second = ++szy;
for(i=1;i<=n;i++) p[i].a = mpx[p[i].a], p[i].b = mpx[p[i].b];
for(i=1;i<=n;i++) p[i].c = mpy[p[i].c], p[i].d = mpy[p[i].d];
}
pii combine(pii x,pii y) {
if(x.first==y.first) return {x.first,(x.second+y.second+mod)%mod};
if(x.first>y.first) return x;
return y;
}
void add(int x,pii val) {
while(x>0) {
tree[x] = combine(tree[x],val);
x -= x&-x;
}
}
pii query(int x) {
pii ans;
ans = {0,0};
while(x<=szy+5) {
ans = combine(ans,tree[x]);
x += x&-x;
}
return ans;
}
main() {
int i,x,pos;
pii ans;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);
cpidx();
for(i=1;i<=n;i++) ass[p[i].a].push_back(i), hole[p[i].b].push_back(i);
add(szy+1,{0,1});
for(pos=szx;pos>0;pos--) {
// printf("TIME = %d\n",pos);
for(i=0;i<ass[pos].size();i++) {
x = ass[pos][i];
// printf("------ add %d {%d, %d}\n",x,val[x].first,val[x].second);
add(p[x].c,val[x]);
}
for(i=0;i<hole[pos].size();i++) {
x = hole[pos][i];
val[x] = query(p[x].d+1);
val[x].first++;
// printf("---------------------- val %d = {%d, %d}\n",x,val[x].first,val[x].second);
}
}
ans = query(1);
printf("%d %d",ans.first,ans.second);
}
Compilation message
trapezoid.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<ass[pos].size();i++) {
^
trapezoid.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<hole[pos].size();i++) {
^
trapezoid.cpp:50:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
trapezoid.cpp:51:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
17648 KB |
Output is correct |
| 2 |
Correct |
6 ms |
17648 KB |
Output is correct |
| 3 |
Correct |
3 ms |
17780 KB |
Output is correct |
| 4 |
Correct |
9 ms |
17912 KB |
Output is correct |
| 5 |
Correct |
6 ms |
18176 KB |
Output is correct |
| 6 |
Correct |
13 ms |
18440 KB |
Output is correct |
| 7 |
Correct |
13 ms |
18704 KB |
Output is correct |
| 8 |
Correct |
13 ms |
18968 KB |
Output is correct |
| 9 |
Correct |
29 ms |
20156 KB |
Output is correct |
| 10 |
Correct |
79 ms |
22664 KB |
Output is correct |
| 11 |
Correct |
76 ms |
23852 KB |
Output is correct |
| 12 |
Correct |
173 ms |
30188 KB |
Output is correct |
| 13 |
Correct |
226 ms |
32696 KB |
Output is correct |
| 14 |
Correct |
319 ms |
35204 KB |
Output is correct |
| 15 |
Correct |
396 ms |
36392 KB |
Output is correct |
| 16 |
Correct |
426 ms |
37712 KB |
Output is correct |
| 17 |
Correct |
413 ms |
38900 KB |
Output is correct |
| 18 |
Correct |
376 ms |
40220 KB |
Output is correct |
| 19 |
Correct |
373 ms |
41408 KB |
Output is correct |
| 20 |
Correct |
436 ms |
42728 KB |
Output is correct |
