#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <iomanip>
#include <bitset>
//#include "molecules.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);
struct s {
int x, y, x1, y1;
};
bool comp(s a, s b) {
return min(a.x, a.x1) < min(b.x, b.x1);
}
const int MAXN = 1e5 + 5;
int BIT[MAXN];
void update(int idx, int val) {
for (; idx < MAXN; idx += idx & -idx) {
BIT[idx] = max(BIT[idx], val);
}
}
int query(int idx) {
int ret = 0;
for (; idx > 0; idx -= idx & -idx) {
ret = max(ret, BIT[idx]);
}
return ret;
}
int dp[MAXN];
ll ways[MAXN];
const int MOD = 30013;
int main() {
int n;
cin >> n;
vector<pair<pair<int, int>, pair<int, int>>> nums;
map<int, int> cc;
vector<int> p;
for (int i = 0; i < n; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
p.push_back(a);
p.push_back(b);
p.push_back(c);
p.push_back(d);
nums.push_back({ {a, b}, {c, d} });
}
sort(p.begin(), p.end());
sort(nums.begin(), nums.end());
int cnt = 1;
for (int i = 0; i < nums.size(); i++) {
if (cc.find(p[i]) != cc.end()) {
continue;
}
cc[p[i]] = cnt;
cnt++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
ways[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j].first.second < nums[i].first.first && nums[j].second.second < nums[i].second.first) {
if (dp[j] > dp[i]) {
dp[i] = dp[j];
ways[i] = ways[j];
}
else if (dp[i] == dp[j]) {
ways[i] = (ways[i] + ways[j])%MOD;
}
}
}
dp[i]++;
ans = max(ans, dp[i]);
//dp[i] = max(dp[i], dp[i - 1]);
}
ll tot = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == ans) {
tot = (tot + ways[i])%MOD;
}
}
cout << ans << " " << tot << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < nums.size(); i++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
5 ms |
364 KB |
Output is correct |
5 |
Correct |
11 ms |
492 KB |
Output is correct |
6 |
Correct |
22 ms |
620 KB |
Output is correct |
7 |
Correct |
54 ms |
620 KB |
Output is correct |
8 |
Correct |
46 ms |
748 KB |
Output is correct |
9 |
Correct |
190 ms |
1128 KB |
Output is correct |
10 |
Execution timed out |
1086 ms |
1764 KB |
Time limit exceeded |
11 |
Execution timed out |
1085 ms |
2812 KB |
Time limit exceeded |
12 |
Execution timed out |
1090 ms |
4440 KB |
Time limit exceeded |
13 |
Execution timed out |
1088 ms |
5208 KB |
Time limit exceeded |
14 |
Execution timed out |
1095 ms |
6120 KB |
Time limit exceeded |
15 |
Execution timed out |
1099 ms |
5840 KB |
Time limit exceeded |
16 |
Execution timed out |
1080 ms |
6492 KB |
Time limit exceeded |
17 |
Execution timed out |
1085 ms |
7076 KB |
Time limit exceeded |
18 |
Execution timed out |
1078 ms |
5712 KB |
Time limit exceeded |
19 |
Execution timed out |
1086 ms |
7548 KB |
Time limit exceeded |
20 |
Execution timed out |
1082 ms |
7760 KB |
Time limit exceeded |