This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
using namespace std;
const int N = 1e5 + 7;
int l[N], r[N], u[N], d[N], a[N], minst[N], maxdr[N];
/*
3
-1 2 0
-1 0 1
2 2 1
0 0 1
*/
int main()
{
int n;
bool ok(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> l[i];
if (l[i] == -1)
l[i] = n;
}
for (int i = 1; i <= n; ++i) {
cin >> r[i];
if (r[i] == -1)
r[i] = n;
}
for (int i = 1; i <= n; ++i) {
cin >> u[i];
if (u[i] == -1)
u[i] = n;
}
for (int i = 1; i <= n; ++i) {
cin >> d[i];
if (d[i] == -1)
d[i] = n;
}
for (int i = 1; i <= n; ++i)
minst[i] = 1e9 + 7, maxdr[i] = -1;
for (int i = 1; i <= n; ++i) {
minst[n - d[i]] = min(minst[n - d[i]], i);
maxdr[u[i] + 1] = max(minst[u[i] + 1], i);
}
for (int i = 1; i <= n; ++i) {
if (minst[i] <= l[i])
ok = 1;
if (u[l[i] + 1] > i)
ok = 1;
if (d[l[i] + 1] > n - i)
ok = 1;
if (maxdr[i] != -1 && n - maxdr[i] > r[i])
ok = 1;
if (u[n - r[i]] > i)
ok = 1;
if (d[n - r[i]] > n - i)
ok = 1;
}
for (int i = 1; i <= n; ++i)
a[i] = l[i];
for (int i = 1; i <= n; ++i)
l[i] = u[n - i + 1];
for (int i = 1; i <= n; ++i)
u[i] = r[i];
for (int i = 1; i <= n; ++i)
r[i] = d[n - i + 1];
for (int i = 1; i <= n; ++i)
d[i] = a[i];
for (int i = 1; i <= n; ++i)
minst[i] = 1e9 + 7, maxdr[i] = -1;
for (int i = 1; i <= n; ++i) {
minst[n - d[i]] = min(minst[n - d[i]], i);
maxdr[u[i] + 1] = max(minst[u[i] + 1], i);
}
for (int i = 1; i <= n; ++i) {
if (minst[i] <= l[i])
ok = 1;
if (u[l[i] + 1] > i)
ok = 1;
if (d[l[i] + 1] > n - i)
ok = 1;
if (maxdr[i] != -1 && n - maxdr[i] > r[i])
ok = 1;
if (u[n - r[i]] > i)
ok = 1;
if (d[n - r[i]] > n - i)
ok = 1;
}
if (ok) {
cout << "NE";
}
else {
cout << "DA";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |