#include <iostream>
#include <algorithm>
#include <stack>
#include <string.h>
using namespace std;
using ll = long long;
const ll mod = 30013;
int n, a, b, c, d, cn, ec;
ll comp[200099];
struct Da{
ll ma, cn;
Da operator +(const Da &k){
Da tmp;
tmp.ma = max(ma, k.ma);
if(ma == k.ma) tmp.cn = (cn + k.cn) % mod;
else if(ma > k.ma) tmp.cn = cn;
else tmp.cn = k.cn;
return tmp;
}
Da pp(){
Da tmp = {ma + 1, cn};
return tmp;
}
};
Da res[100099];
struct Eve{
int t, ind, ui, x, y;
bool operator <(const Eve &a) const{
return ui < a.ui;
}
} events[200099];
struct Segtree{
Da tree[800099];
void init(int node, int s, int e){
tree[node] = {0, 1};
if(s == e) return;
int mid = (s + e) / 2;
init(node * 2, s, mid);
init(node * 2 + 1, mid + 1, e);
}
void update(int node, int s, int e, int qi, Da qv){
if(qi < s || e < qi) return;
if(s == e){
tree[node] = tree[node] + qv;
return;
}
int mid = (s + e) / 2;
update(node * 2, s, mid, qi, qv);
update(node * 2 + 1, mid + 1, e, qi, qv);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
Da query(int node, int s, int e, int qs, int qe){
if(qe < s || e < qs) return {0, 0};
if(qs <= s && e <= qe) return tree[node];
int mid = (s + e) / 2;
return query(node * 2, s, mid, qs, qe) + query( node * 2 + 1, mid + 1, e, qs, qe);
}
} bsegt;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d %d %d %d", &a, &b, &c, &d);
if(a > b) swap(a, b);
if(c > d) swap(c, d);
comp[++cn] = c;
comp[++cn] = d;
events[++ec] = {1, i, a, c, d};
events[++ec] = {2, i, b, c, d};
}
sort(events + 1, events + ec + 1);
for(int i = 1; i <= ec; i ++){
events[i].x = lower_bound(comp + 1, comp + cn + 1, events[i].x) - comp;
events[i].y = lower_bound(comp + 1, comp + cn + 1, events[i].y) - comp;
if(events[i].t == 1){
res[events[i].ind] = bsegt.query(1, 1, cn, 1, events[i].x - 1).pp();
if(res[events[i].ind].ma == 1) res[events[i].ind].cn = 1;
}
else{
bsegt.update(1, 1, cn, events[i].y, res[events[i].ind]);
}
}
Da ret = {0, 1};
for(int i = 1; i <= n; i ++){
ret = ret + res[i];
}
printf("%lld %lld", ret.ma, ret.cn);
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
trapezoid.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d %d %d %d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
| 2 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
6640 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
6748 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
6836 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
6748 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
7004 KB |
Output isn't correct |
| 10 |
Incorrect |
14 ms |
7772 KB |
Output isn't correct |
| 11 |
Incorrect |
17 ms |
7772 KB |
Output isn't correct |
| 12 |
Incorrect |
38 ms |
9124 KB |
Output isn't correct |
| 13 |
Incorrect |
51 ms |
9560 KB |
Output isn't correct |
| 14 |
Incorrect |
70 ms |
10504 KB |
Output isn't correct |
| 15 |
Incorrect |
61 ms |
11860 KB |
Output isn't correct |
| 16 |
Incorrect |
59 ms |
10064 KB |
Output isn't correct |
| 17 |
Incorrect |
63 ms |
10836 KB |
Output isn't correct |
| 18 |
Incorrect |
72 ms |
11636 KB |
Output isn't correct |
| 19 |
Incorrect |
71 ms |
11600 KB |
Output isn't correct |
| 20 |
Incorrect |
74 ms |
11432 KB |
Output isn't correct |
