#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;
const int INF = 1e9 + 5;
struct node {
node *left, *right;
ii val;
node(ii v, node *l, node *r) {
val = v;
left = l;
right = r;
}
node *ins(int L, int R, int x, ii v);
} *root[MAXN];
node *null = new node(mp(0, 0), NULL, NULL);
ii combine(ii lhs, ii rhs) {
if (lhs.fi == rhs.fi)
return mp(lhs.fi, (lhs.se + rhs.se) % MOD);
return max(lhs, rhs);
}
node* node::ins(int L, int R, int x, ii v) {
if (L == R)
return new node(combine(val, v), null, null);
int mid = (L + R) >> 1;
/*ii cur = val;
if (v > cur)
cur = v;
else if (v.fi == cur.fi)
cur.se += v.se, cur.se %= MOD;*/
if (x <= mid)
return new node(combine(val, v), left->ins(L, mid, x, v), right);
else
return new node(combine(val, v), left, right->ins(mid + 1, R, x, v));
}
ii query(node *p, int L, int R, int i, int j) {
if (i > R || j < L) return mp(0, 0);
if (i <= L && j >= R)
return p->val;
int mid = (L + R) >> 1;
return combine(query(p->left, L, mid, i, j), query(p->right, mid + 1, R, i, j));
/*ii lval = query(p->left, L, mid, i, j);
ii rval = query(p->right, mid + 1, R, i, j);
ii ret = mp(0, 0);
if (lval.fi == rval.fi)
ret = mp(lval.fi, (lval.se + rval.se) % MOD);
else
ret = max(lval, rval);
return ret;*/
}
int p[MAXN], a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[MAXN], cnt[MAXN];
inline bool comp(int x, int y) {
if (b[x] == b[y])
return d[x] < d[y];
return b[x] < b[y];
}
int getit(int lo, int hi, int x) {
int res = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (b[p[mid]] < x) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return res;
}
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n;
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, comp);
null->left = null->right = null;
dp[0] = 1;
cnt[0] = 1;
root[0] = null->ins(1, INF, d[0], mp(1, 1));
#if 0
printf("sorted:\n");
for (int i = 0; i < n; i++) {
printf("%d %d %d %d\n", a[p[i]], b[p[i]], c[p[i]], d[p[i]]);
}
#endif
#if 0
for (int i = 1; i < n; i++) {
int pos = p[i];
cnt[i] = 0;
dp[i] = 0;
int what = getit(0, i - 1, a[p[i]]);
/*swap(a[pos], b[pos]);
int what = lower_bound(p, p + i, i, comp) - p - 1;
swap(a[pos], b[pos]);*/
for (int j = 0; j <= what; j++) {
if (d[p[j]] < c[pos]) {
dp[i] = max(dp[i], dp[j]);
}
}
for (int j = 0; j <= what; j++) {
if (d[p[j]] < c[pos] && dp[i] == dp[j]) {
cnt[i] = (cnt[i] + cnt[j]) % MOD;
}
}
dp[i]++;
if (dp[i] == 1) cnt[i] = 1;
}
#if 0
for (int i = 0; i < n; i++) {
printf("%d) dp: %d, cnt: %d\n", i, dp[i], cnt[i]);
}
#endif
int mx = *max_element(dp, dp + n), ans = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == mx) ans = (ans + cnt[i]) % MOD;
}
printf("%d %d\n", mx, ans);
#endif
#if 1
for (int i = 1; i < n; i++) {
int pos = p[i];
int what = getit(0, i - 1, a[pos]);
//swap(a[pos], b[pos]);
//int what = lower_bound(p, p + i, i, comp) - p - 1;
//swap(a[pos], b[pos]);
//printf("for pos %d what is %d\n", pos, what);
ii cur = query(root[what], 1, INF, 1, c[pos] - 1);
dp[i] = cur.fi + 1;
cnt[i] = (cur.se + (dp[i] == 1 ? 1 : 0)) % MOD;
#if 0
cur = query(root[i - 1], 1, INF, d[pos], d[pos]);
if (cur.fi == dp[i])
cur.se = (cur.se + cnt[i]) % MOD;
else
cur = mp(dp[i], cnt[i]);
#endif
root[i] = root[i - 1]->ins(1, INF, d[pos], mp(dp[i], cnt[i]));
}
ii ans = query(root[n - 1], 1, INF, 1, INF);
printf("%d %d\n", ans.fi, ans.se);
#endif
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:139:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
trapezoid.cpp:141: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 |
5540 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5672 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6068 KB |
Output is correct |
| 4 |
Partially correct |
3 ms |
6464 KB |
Partially correct |
| 5 |
Correct |
0 ms |
7520 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8444 KB |
Output is correct |
| 7 |
Partially correct |
13 ms |
9368 KB |
Partially correct |
| 8 |
Correct |
16 ms |
10424 KB |
Output is correct |
| 9 |
Correct |
26 ms |
15176 KB |
Output is correct |
| 10 |
Partially correct |
53 ms |
24944 KB |
Partially correct |
| 11 |
Correct |
73 ms |
29696 KB |
Output is correct |
| 12 |
Correct |
159 ms |
53852 KB |
Output is correct |
| 13 |
Correct |
169 ms |
63488 KB |
Output is correct |
| 14 |
Memory limit exceeded |
193 ms |
65536 KB |
Memory limit exceeded |
| 15 |
Memory limit exceeded |
229 ms |
65536 KB |
Memory limit exceeded |
| 16 |
Memory limit exceeded |
296 ms |
65536 KB |
Memory limit exceeded |
| 17 |
Memory limit exceeded |
256 ms |
65536 KB |
Memory limit exceeded |
| 18 |
Memory limit exceeded |
159 ms |
65536 KB |
Memory limit exceeded |
| 19 |
Memory limit exceeded |
209 ms |
65536 KB |
Memory limit exceeded |
| 20 |
Memory limit exceeded |
216 ms |
65536 KB |
Memory limit exceeded |
