#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e5 + 1;
const int mod = 30013;
pair<int, int> t[N * 8], dp[N];
void upd(int v, int tl, int tr, int pos, pair<int, int> val){
if(tl > pos || pos > tr)
return;
if(tl == tr)
return void(t[v] = val);
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, pos, val);
upd(v * 2 + 1, tm + 1, tr, pos, val);
if(t[v * 2].X > t[v * 2 + 1].X)
t[v] = t[v * 2];
else if(t[v * 2].X < t[v * 2 + 1].X)
t[v] = t[v * 2 + 1];
else
t[v] = MP(t[v * 2].X, (t[v * 2].Y + t[v * 2 + 1].Y) % mod);
}
pair<int, int> get(int v, int tl, int tr, int l, int r){
if(tl > r || l > tr)
return MP(0, 0);
if(tl >= l && tr <= r)
return t[v];
int tm = (tl + tr) / 2;
pair<int, int> left = get(v * 2, tl, tm, l, r), right = get(v * 2 + 1, tm + 1, tr, l, r);
if(left.X > right.X)
return left;
else if(left.X < right.X)
return right;
else
return MP(left.X, (left.Y + right.Y) % mod);
}
int a[4][N], n, m;
void shrink(){
vector< pair< int, pair<int, int> > > tmp;
scanf("%d", &n);
for(int i = 1;i <= n;i++)
for(int j = 0;j < 4;j++){
scanf("%d", &a[j][i]);
if(j > 1)
tmp.push_back(MP(a[j][i], MP(j, i)));
}
sort(tmp.begin(), tmp.end());
for(int i = 0;i < 2 * n;i++){
if(i == 0 || tmp[i - 1].X != tmp[i].X)
m++;
a[tmp[i].Y.X][tmp[i].Y.Y] = m;
}
}
int main () {
shrink();
vector<int> tmp;
int len = 0, ans = 0;
for(int i = 1;i <= n;i++)
tmp.push_back(i), tmp.push_back(-i);
sort(tmp.begin(), tmp.end(), [](int x, int y){
x = x > 0?a[1][x]:a[0][-x];
y = y > 0?a[1][y]:a[0][-y];
return x < y;
});
for(int v: tmp){
if(v < 0){
v = -v;
dp[v] = get(1, 1, m, 1, a[2][v]);
dp[v].X += 1;
if(dp[v].X == 1)
dp[v].Y += 1;
if(dp[v].X > len)
len = dp[v].X, ans = dp[v].Y;
else if(dp[v].X == len)
ans = (ans + dp[v].Y) % mod;
}
else{
upd(1, 1, m, a[3][v], dp[v]);
}
}
printf("%d %d", len, ans);
}
Compilation message
trapezoid.cpp: In function 'void shrink()':
trapezoid.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
46 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
trapezoid.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
49 | scanf("%d", &a[j][i]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
4 ms |
748 KB |
Output is correct |
| 6 |
Correct |
5 ms |
736 KB |
Output is correct |
| 7 |
Correct |
7 ms |
812 KB |
Output is correct |
| 8 |
Correct |
8 ms |
968 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1532 KB |
Output is correct |
| 10 |
Correct |
30 ms |
2956 KB |
Output is correct |
| 11 |
Correct |
39 ms |
2968 KB |
Output is correct |
| 12 |
Correct |
102 ms |
5836 KB |
Output is correct |
| 13 |
Correct |
124 ms |
6512 KB |
Output is correct |
| 14 |
Correct |
119 ms |
9572 KB |
Output is correct |
| 15 |
Correct |
135 ms |
9840 KB |
Output is correct |
| 16 |
Correct |
150 ms |
10120 KB |
Output is correct |
| 17 |
Correct |
153 ms |
10500 KB |
Output is correct |
| 18 |
Correct |
159 ms |
10656 KB |
Output is correct |
| 19 |
Correct |
155 ms |
10396 KB |
Output is correct |
| 20 |
Correct |
172 ms |
11048 KB |
Output is correct |
