#include<iostream>
#include<algorithm>
#define DIM 100005
#define f first
#define s second
#define mod 30013
using namespace std;
int n, i, u, k, ind;
int w[2 * DIM], d[DIM], num[DIM];
pair<int, int> p[DIM], aint[4 * DIM], curr;
struct str{
int a, b, c, d;
};
str v[DIM];
int cmp(str x, str y){
return x.a < y.a;
}
int cautbin(int x){
int st = 1, dr = k, mid;
while(st <= dr){
mid = (st + dr) / 2;
if(w[mid] == x){
return mid;
}
if(w[mid] < x){
st = mid + 1;
}
else{
dr = mid - 1;
}
}
}
void update(int nod, int st, int dr, int p, int x, int y){
if(st == dr){
aint[nod] = make_pair(x, y);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p, x, y);
}
else{
update(2 * nod + 1, mid + 1, dr, p, x, y);
}
if(aint[2 * nod].f == aint[2 * nod + 1].f){
aint[nod].f = aint[2 * nod].f;
aint[nod].s = (aint[2 * nod].s + aint[2 * nod + 1].s) % mod;
}
else{
if(aint[2 * nod].f > aint[2 * nod + 1].f){
aint[nod] = aint[2 * nod];
}
else{
aint[nod] = aint[2 * nod + 1];
}
}
}
}
void query(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
if(curr.f < aint[nod].f){
curr = aint[nod];
}
else{
if(curr.f == aint[nod].f){
curr.s = (curr.s + aint[nod].s) % mod;
}
}
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
query(2 * nod, st, mid, p, u);
}
if(u > mid){
query(2 * nod + 1, mid + 1, dr, p, u);
}
}
}
int main(){
cin>> n;
for(i = 1; i <= n; i++){
cin>> v[i].a >> v[i].b >> v[i].c >> v[i].d;
w[2 * i - 1] = v[i].c;
w[2 * i] = v[i].d;
}
k = 2 * n;
sort(w + 1, w + k + 1);
for(i = 1; i <= n; i++){
v[i].c = cautbin(v[i].c);
v[i].d = cautbin(v[i].d);
}
sort(v + 1, v + n + 1, cmp);
for(i = 1; i <= n; i++){
p[i] = make_pair(v[i].b, i);
}
sort(p + 1, p + n + 1);
u = 1;
for(i = 1; i <= n; i++){
while(u <= n && p[u].f < v[i].a){
ind = p[u].s;
u++;
update(1, 1, k, v[ind].d, d[ind], num[ind]);
}
curr = make_pair(0, 0);
query(1, 1, k, 1, v[i].c);
if(curr.f == 0){
d[i] = num[i] = 1;
}
else{
d[i] = curr.f + 1;
num[i] = curr.s;
}
}
while(u <= n){
ind = p[u].s;
u++;
update(1, 1, k, v[ind].d, d[ind], num[ind]);
}
cout<< aint[1].f <<" "<< aint[1].s;
return 0;
}
Compilation message
trapezoid.cpp: In function 'int cautbin(int)':
trapezoid.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
6 ms |
376 KB |
Output is correct |
| 4 |
Correct |
7 ms |
376 KB |
Output is correct |
| 5 |
Correct |
9 ms |
504 KB |
Output is correct |
| 6 |
Correct |
12 ms |
632 KB |
Output is correct |
| 7 |
Correct |
14 ms |
764 KB |
Output is correct |
| 8 |
Correct |
17 ms |
888 KB |
Output is correct |
| 9 |
Correct |
29 ms |
1528 KB |
Output is correct |
| 10 |
Correct |
56 ms |
2808 KB |
Output is correct |
| 11 |
Correct |
70 ms |
2936 KB |
Output is correct |
| 12 |
Correct |
148 ms |
5744 KB |
Output is correct |
| 13 |
Correct |
173 ms |
6372 KB |
Output is correct |
| 14 |
Incorrect |
201 ms |
8568 KB |
Output isn't correct |
| 15 |
Incorrect |
215 ms |
8568 KB |
Output isn't correct |
| 16 |
Runtime error |
233 ms |
15352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Incorrect |
250 ms |
9208 KB |
Output isn't correct |
| 18 |
Incorrect |
246 ms |
9464 KB |
Output isn't correct |
| 19 |
Incorrect |
264 ms |
9592 KB |
Output isn't correct |
| 20 |
Incorrect |
287 ms |
9972 KB |
Output isn't correct |
