#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005, Mod = 30013;
int n, A[N], B[N], C[N], D[N], P[N], dp[N], cn[N];
set < pair < int , int > > S, TB;
vector < int > vec[N], F[N];
inline bool CMP(int i, int j)
{
return (A[i] < A[j]);
}
inline void Add(vector < int > &G, int i, int vl)
{
for (i ++; i <= (int)G.size(); i += i & -i)
{
G[i] += vl;
if (G[i] >= Mod)
G[i] -= Mod;
}
}
inline int Get(vector < int > &G, int i)
{
int rt = 0;
for (i ++; i; i -= i & -i)
{
rt += G[i];
if (rt >= Mod)
rt -= Mod;
}
return (rt);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]), P[i] = i;
sort(P, P + n, CMP);
for (int j = 0; j < n; j++)
{
int i = P[j];
dp[i] = 1;
while (TB.size() && TB.begin()->first < A[i])
{
int id = TB.begin()->second;
TB.erase(TB.begin());
auto it = S.lower_bound(make_pair(D[id], 0));
while (it != S.end())
{
if (it->second > dp[id])
break;
it = S.erase(it);
}
if (it != S.begin())
{
it --;
if (it->second >= dp[id])
continue;
}
S.insert(make_pair(D[id], dp[id]));
}
auto it = S.lower_bound(make_pair(C[i], 0));
if (it != S.begin())
it --, dp[i] = it->second + 1;
TB.insert(make_pair(B[i], i));
vec[dp[i]].push_back(D[i]);
}
for (int i = 1; i <= n; i++)
sort(vec[i].begin(), vec[i].end()), F[i].resize((int)vec[i].size() + 5);
TB.clear();
for (int j = 0; j < n; j++)
{
int i = P[j];
while (TB.size() && TB.begin()->first < A[i])
{
int id = TB.begin()->second;
TB.erase(TB.begin());
int lb = lower_bound(vec[dp[id]].begin(), vec[dp[id]].end(), D[id]) - vec[dp[id]].begin();
Add(F[dp[id]], lb, cn[id]);
}
if (dp[i] > 1)
{
int lb = upper_bound(vec[dp[i] - 1].begin(), vec[dp[i] - 1].end(), C[i]) - vec[dp[i] - 1].begin() - 1;
cn[i] = Get(F[dp[i] - 1], lb);
}
else
cn[i] = 1;
TB.insert(make_pair(B[i], i));
}
int Mx = 0, cnt = 0;
for (int i = 0; i < n; i++)
{
if (Mx < dp[i])
Mx = dp[i], cnt = 0;
if (Mx == dp[i])
{
cnt += cn[i];
if (cnt >= Mod)
cnt -= Mod;
}
}
return !printf("%d %d\n", Mx, cnt);
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
trapezoid.cpp:36:54: 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]), P[i] = i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 7 |
Correct |
10 ms |
5376 KB |
Output is correct |
| 8 |
Correct |
12 ms |
5504 KB |
Output is correct |
| 9 |
Correct |
18 ms |
5760 KB |
Output is correct |
| 10 |
Correct |
27 ms |
6528 KB |
Output is correct |
| 11 |
Correct |
33 ms |
6780 KB |
Output is correct |
| 12 |
Correct |
64 ms |
8504 KB |
Output is correct |
| 13 |
Correct |
81 ms |
9340 KB |
Output is correct |
| 14 |
Correct |
100 ms |
10032 KB |
Output is correct |
| 15 |
Correct |
112 ms |
10488 KB |
Output is correct |
| 16 |
Correct |
128 ms |
10988 KB |
Output is correct |
| 17 |
Correct |
125 ms |
11256 KB |
Output is correct |
| 18 |
Correct |
112 ms |
11384 KB |
Output is correct |
| 19 |
Correct |
120 ms |
11604 KB |
Output is correct |
| 20 |
Correct |
140 ms |
12124 KB |
Output is correct |
