#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int) (x).size()
const int N = 100005;
int a[N][3], g[3][N];
vector<int> gist[N], fst[N];
int suf[8][N], result[3], ans[N], tmp[N], dp[N], sum[N], DP[8][N][3];
vector<int> gr[8][N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int j = 0; j < 3; j++) {
for (int i = 0; i < n; i++) {
cin >> g[j][i];
g[j][i]--;
a[g[j][i]][j] = i;
}
}
for (int i = 0; i < n; i++) {
dp[i] = min({a[i][0], a[i][1], a[i][2]});
gist[dp[i]].push_back(i);
int msk = 0;
if (dp[i] == a[i][0]) msk += 1;
if (dp[i] == a[i][1]) msk += 2;
if (dp[i] == a[i][2]) msk += 4;
suf[msk][dp[i] + 1]++;
gr[msk][dp[i] + 1].push_back(i);
}
for (int msk = 1; msk < 8; msk++) {
for (int i = 0; i < n; i++) {
if (i) suf[msk][i] += suf[msk][i - 1];
for (auto x : gist[i]) {
pii res = {N, N};
for (int j = 0; j < 3; j++) {
if (msk >> j & 1) {
res = min(res, {a[x][j], j});
}
}
DP[msk][i][res.se]++;
}
}
}
for (int msk = 1; msk < 8; msk++) {
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 3; j++) {
DP[msk][i][j] += DP[msk][i + 1][j];
for (auto v : gr[msk][i]) {
ans[v] += DP[msk][i][j];
result[j] += DP[msk][i][j];
}
}
}
}
set<pii> used;
for (int i = 0; i < n; i++) {
for (auto x : gist[i]) {
for (auto y : gist[i]) {
if (x >= y || used.find({x, y}) != used.end()) continue;
pii res = {min(a[x][0], a[y][0]), max(a[x][0], a[y][0])};
pii res2 = {min(a[x][1], a[y][1]), max(a[x][1], a[y][1])};
pii res3 = {min(a[x][2], a[y][2]), max(a[x][2], a[y][2])};
used.insert({x, y});
if (res <= res2 && res <= res3) {
result[0]++;
if (a[x][0] < a[y][0]) {
ans[x]++;
}
else {
ans[y]++;
}
}
else if (res2 <= res3) {
result[1]++;
if (a[x][1] < a[y][1]) {
ans[x]++;
}
else {
ans[y]++;
}
}
else {
result[2]++;
if (a[x][2] < a[y][2]) {
ans[x]++;
}
else {
ans[y]++;
}
}
}
}
}
cout << result[0] << " " << result[1] << " " << result[2] << '\n';
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
23884 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23984 KB |
Output is correct |
| 3 |
Correct |
11 ms |
24012 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
23884 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23984 KB |
Output is correct |
| 3 |
Correct |
11 ms |
24012 KB |
Output is correct |
| 4 |
Correct |
14 ms |
25036 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
23884 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23984 KB |
Output is correct |
| 3 |
Correct |
11 ms |
24012 KB |
Output is correct |
| 4 |
Correct |
14 ms |
25036 KB |
Output is correct |
| 5 |
Correct |
51 ms |
39568 KB |
Output is correct |
| 6 |
Correct |
77 ms |
47428 KB |
Output is correct |
| 7 |
Correct |
116 ms |
55296 KB |
Output is correct |
| 8 |
Correct |
149 ms |
63028 KB |
Output is correct |
| 9 |
Correct |
125 ms |
62272 KB |
Output is correct |
| 10 |
Correct |
114 ms |
60816 KB |
Output is correct |
