| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 908657 | duckindog | 사다리꼴 (balkan11_trapezoid) | C++14 | 117 ms | 60172 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// from duckindog wth depression
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10,
M = 30013;
struct rec {
int a = 0, b = 0, c = 0, d = 0;
bool operator < (const rec& rhs) {
return make_pair(b, d) < make_pair(rhs.b, rhs.b);
}
} r[N];
int n;
bool crossed(rec x, rec y) {
if (min(x.a, x.c) > min(y.a, y.c)) swap(x, y);
return (x.b >= y.a || x.d >= y.c);
}
vector<int> remind[N];
vector<int> rrh;
using pii = pair<int, int>;
pair<int, int> f[4 * N];
void update(int s, int l, int r, pii x, int y) {
if (y < l || y > r) return;
if (l == r) {
f[s] = max(f[s], x);
return;
}
int mid = l + r >> 1;
update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
int ma = max(f[s * 2].first, f[s * 2 + 1].first);
f[s].first = ma;
f[s].second = (f[s * 2].second * (f[s * 2].first == ma) + f[s * 2 + 1].second * (f[s * 2 + 1].first == ma)) % M;
}
pii query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return {0, 0};
if (u <= l && r <= v) return f[s];
int mid = l + r >> 1;
auto lt = query(s * 2, l, mid, u, v), rt = query(s * 2 + 1, mid + 1, r, u, v);
int ma = max(lt.first, rt.first);
return {ma, (lt.second * (lt.first == ma) + rt.second * (rt.first == ma)) % M};
}
pii dp[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("duck.inp", "r")) {
freopen("duck.inp", "r", stdin);
freopen("duck.out", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
r[i] = {a, b, c, d};
}
sort(r + 1, r + n + 1);
for (int i = 1; i <= n; ++i) {
int a = r[i].a, b = r[i].b;
int lt = 0, rt = i - 1, it = 0;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (r[mid].b <= a) lt = (it = mid) + 1;
else rt = mid - 1;
}
remind[it].push_back(i);
}
dp[0] = {0, 1};
for (int i = 0; i <= n; ++i) {
update(1, 0, 1e6, dp[i], r[i].d);
for (auto x : remind[i]) {
int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
dp[x] = query(1, 0, 1e6, 0, c);
dp[x].first += 1;
}
}
auto answer = query(1, 0, 1e6, 0, 1e6);
cout << answer.first << ' ' << 0;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||