#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int MAXN = 1e5 + 5;
const int MOD = 30013;
struct side {
int l, r, idx;
bool right_end;
};
inline bool comp(const side &lhs, const side &rhs) {
if (lhs.l == rhs.l) {
if (lhs.r == rhs.r)
return lhs.right_end < rhs.right_end;
return lhs.r < rhs.r;
}
return lhs.l < rhs.l;
}
vector<side> seg;
vector<side> sec_seg;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[MAXN], cnt[MAXN];
vi cc;
inline bool comp_dp(const side &lhs, const side &rhs) {
if (dp[lhs.idx] == dp[rhs.idx]) {
if (lhs.l == rhs.l)
return lhs.right_end < rhs.right_end;
return lhs.l < rhs.l;
}
return dp[lhs.idx] < dp[rhs.idx];
}
int bit_max[MAXN * 2], bit_sum[MAXN * 2];
#define lsone(s) (s & (-s))
void add_max(int b, int val) {
while (b < MAXN * 2) {
bit_max[b] = max(bit_max[b], val);
b += lsone(b);
}
}
int ask_max(int b) {
int res = 0;
while (b > 0) {
res = max(res, bit_max[b]);
b -= lsone(b);
}
return res;
}
void add_sum(int b, int val) {
b++;
while (b < MAXN * 2) {
bit_sum[b] = (bit_sum[b] + val) % MOD;
b += lsone(b);
}
}
int ask_sum(int b) {
b++;
int res = 0;
while (b > 0) {
res = (res + bit_sum[b]) % MOD;
b -= lsone(b);
}
return res;
}
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n;
scanf("%d", &n);
cc.pb(0);
for (int i = 1; i <= n; i++) {
scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
cc.pb(c[i]);
cc.pb(d[i]);
}
sort(all(cc));
cc.resize(unique(all(cc)) - cc.begin());
seg.reserve(2 * n + 1);
seg.pb((side){0, 0, 0, true});
for (int i = 1; i <= n; i++) {
c[i] = lower_bound(all(cc), c[i]) - cc.begin();
d[i] = lower_bound(all(cc), d[i]) - cc.begin();
seg.pb((side){a[i], c[i], i, false});
seg.pb((side){b[i], d[i], i, true});
}
seg.pb((side){(int)1e9 + 5, 2 * n + 5, n + 1, false});
sort(all(seg), comp);
vii vec;
vec.pb(mp(0, 0));
for (int i = 1; i < (int)seg.size(); i++) {
auto it = seg[i];
if (it.right_end) {
add_max(it.r, dp[it.idx]);
} else {
dp[it.idx] = ask_max(it.r - 1) + 1;
}
vec.pb(mp(dp[it.idx], it.r));
}
sort(all(vec));
cnt[0] = 1;
//int last = 0;
for (int i = 0, j = 0; i < (int)seg.size(); i++) {
auto it = seg[i];
if (it.right_end) {
int pos = lower_bound(all(vec), mp(dp[it.idx], it.r)) - vec.begin();
add_sum(pos, cnt[it.idx]);
} else {
int st = lower_bound(all(vec), mp(dp[it.idx] - 1, 0)) - vec.begin();
int en = lower_bound(all(vec), mp(dp[it.idx] - 1, it.r)) - vec.begin();
cnt[it.idx] = ask_sum(en - 1) - ask_sum(st - 1);
}
/*j = i;
while (j < (int)seg.size() && dp[seg[j].idx] == dp[seg[i].idx]) {
auto it = seg[j];
printf("processing %d, right_end? %d\n", it.idx, it.right_end);
j++;
if (it.right_end) continue;
while (last < i && dp[seg[last].idx] < dp[it.idx] - 1) {
if (seg[last].right_end)
add_sum(seg[last].r, -cnt[seg[last].idx]);
last++;
}
cnt[it.idx] = ask_sum(it.r - 1);
printf("last is %d\n", last);
}
j = i;
while (j < (int)seg.size() && dp[seg[j].idx] == dp[seg[i].idx]) {
auto it = seg[j];
if (it.right_end)
add_sum(it.r, cnt[it.idx]);
j++;
}*/
}
#if 0
for (int i = 0; i <= n + 1; i++) {
printf("%d) dp: %d, cnt: %d\n", i, dp[i], cnt[i]);
}
#endif
printf("%d %d\n", dp[n + 1] - 1, cnt[n + 1]);
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:167:21: warning: unused variable 'j' [-Wunused-variable]
for (int i = 0, j = 0; i < (int)seg.size(); i++) {
^
trapezoid.cpp:126:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
trapezoid.cpp:129:57: 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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5932 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5932 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6064 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6120 KB |
Output is correct |
| 5 |
Partially correct |
3 ms |
6104 KB |
Partially correct |
| 6 |
Partially correct |
3 ms |
6260 KB |
Partially correct |
| 7 |
Correct |
3 ms |
6324 KB |
Output is correct |
| 8 |
Partially correct |
6 ms |
6644 KB |
Partially correct |
| 9 |
Partially correct |
13 ms |
7280 KB |
Partially correct |
| 10 |
Correct |
23 ms |
8544 KB |
Output is correct |
| 11 |
Partially correct |
39 ms |
8856 KB |
Partially correct |
| 12 |
Correct |
96 ms |
11700 KB |
Output is correct |
| 13 |
Correct |
103 ms |
12324 KB |
Output is correct |
| 14 |
Correct |
106 ms |
15508 KB |
Output is correct |
| 15 |
Partially correct |
139 ms |
15820 KB |
Partially correct |
| 16 |
Partially correct |
153 ms |
16136 KB |
Partially correct |
| 17 |
Correct |
173 ms |
16448 KB |
Output is correct |
| 18 |
Correct |
143 ms |
16760 KB |
Output is correct |
| 19 |
Partially correct |
176 ms |
17072 KB |
Partially correct |
| 20 |
Partially correct |
196 ms |
17384 KB |
Partially correct |
