#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, D[101000], D2[101000], Mod = 30013, Cnt;
struct IndexTree{
int a, b;
}IT[501000];
struct trapezoid{
int a, b, c, d;
bool operator <(const trapezoid &p)const{
return a < p.a;
}
}w[101000], w2[101000];
struct order{
int a, b;
bool operator <(const order &p)const{
return a < p.a;
}
}ord[201000];
void ins(int a, int b){
while (a){
if (D[IT[a].a] < D[b])IT[a].a = b, IT[a].b = 0;
if (D[IT[a].a] == D[b])IT[a].b = (IT[a].b + D2[b]) % Mod;
a >>= 1;
}
}
int Max(int a, int b){
int r = 0;
Cnt = 0;
while (a <= b){
if (a & 1){
if (D[r] < D[IT[a].a])r = IT[a].a, Cnt = 0;
if (D[r] == D[IT[a].a])Cnt += IT[a].b;
}
if (!(b & 1)){
if (D[r] < D[IT[b].a])r = IT[b].a, Cnt = 0;
if (D[r] == D[IT[b].a])Cnt += IT[b].b;
}
a = (a + 1) >> 1, b = (b - 1) >> 1;
}
Cnt %= Mod;
return D[r];
}
int main()
{
int i, pv = 0, Res = 0, Res2 = 0;
scanf("%d", &n);
for (i = 0; i < n; i++){
scanf("%d%d%d%d", &w[i].a, &w[i].b, &w[i].c, &w[i].d);
}
sort(w, w + n);
for (i = 0; i < n; i++){
ord[i * 2].a = w[i].c, ord[i * 2].b = i * 2;
ord[i * 2 + 1].a = w[i].d, ord[i * 2 + 1].b = i * 2 + 1;
}
sort(ord, ord + n * 2);
for (i = 0; i < 2 * n; i++){
if (ord[i].b & 1)w[ord[i].b >> 1].d = i;
else w[ord[i].b >> 1].c = i;
}
for (i = 0; i < n; i++){
w2[i] = w[i];
swap(w2[i].a, w2[i].b);
w2[i].c = i;
}
sort(w2, w2 + n);
for (i = 0; i < n; i++){
while (w[i].a>w2[pv].a){
ins(SZ+w2[pv].d, w2[pv].c+1);
pv++;
}
D[i + 1] = Max(SZ, SZ + w[i].c) + 1;
D2[i + 1] = Cnt;
if (!D2[i + 1])D2[i + 1] = 1;
if (Res < D[i + 1])Res = D[i + 1], Res2 = 0;
if (Res == D[i + 1])Res2 = (Res2 + D2[i + 1]) % Mod;
}
printf("%d %d\n", Res, Res2);
}
Compilation message
trapezoid.cpp:1:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:49:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
trapezoid.cpp:51:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &w[i].a, &w[i].b, &w[i].c, &w[i].d);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10548 KB |
Output is correct |
| 2 |
Correct |
0 ms |
10548 KB |
Output is correct |
| 3 |
Correct |
0 ms |
10548 KB |
Output is correct |
| 4 |
Correct |
0 ms |
10548 KB |
Output is correct |
| 5 |
Correct |
0 ms |
10548 KB |
Output is correct |
| 6 |
Correct |
3 ms |
10548 KB |
Output is correct |
| 7 |
Correct |
3 ms |
10548 KB |
Output is correct |
| 8 |
Correct |
3 ms |
10548 KB |
Output is correct |
| 9 |
Correct |
9 ms |
10548 KB |
Output is correct |
| 10 |
Correct |
19 ms |
10548 KB |
Output is correct |
| 11 |
Correct |
23 ms |
10548 KB |
Output is correct |
| 12 |
Correct |
49 ms |
10548 KB |
Output is correct |
| 13 |
Correct |
69 ms |
10548 KB |
Output is correct |
| 14 |
Correct |
73 ms |
10548 KB |
Output is correct |
| 15 |
Correct |
83 ms |
10548 KB |
Output is correct |
| 16 |
Correct |
93 ms |
10548 KB |
Output is correct |
| 17 |
Correct |
89 ms |
10548 KB |
Output is correct |
| 18 |
Correct |
89 ms |
10548 KB |
Output is correct |
| 19 |
Correct |
99 ms |
10548 KB |
Output is correct |
| 20 |
Correct |
119 ms |
10548 KB |
Output is correct |
