#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
const int N = 1e5 + 5;
struct fenwick {
int f[N] {};
void add(int i) {for(i = N - 2 - i; i < N; i += i & -i) ++f[i];}
int get(int i) {int v{}; for(i = N - 2 - i; i; i -= i & -i) v += f[i]; return v;}
};
fenwick f0, f01, f02, f012,
f1, f10, f12, f102,
f2, f20, f21, f201;
int p0[N], p1[N], p2[N], r0[N], r1[N], r2[N], n, p[N];
int c0, c1, c2, s[N];
void add(int &a, int &b, const int c) {
a += c;
b += c;
}
int min(const int a, const int b, const int c) {
return min(a, min(b, c));
}
set<pii> f;
void check(int i, int j) {
if(p[i] != p[j]) return;
f.insert({i, j});
}
void solve() {
cin >> n;
for(int i = 0; i < n; ++i)
cin >> r0[i], p0[--r0[i]] = i;
for(int i = 0; i < n; ++i)
cin >> r1[i], p1[--r1[i]] = i;
for(int i = 0; i < n; ++i)
cin >> r2[i], p2[--r2[i]] = i;
for(int i = 0; i < n; ++i)
p[i] = min(p0[i], p1[i], p2[i]);
for(int i = n - 1; ~i; --i) {
int v;
bool b0, b1;
v = r0[i];
if(p1[v] > i && p2[v] > i) add(c0, s[v], f0 .get(i + 1)), check(v, r1[i]), check(v, r2[i]);
if(p1[v] == i && p2[v] > i) add(c0, s[v], f01 .get(i + 1)), check(v, r2[i]);
if(p1[v] > i && p2[v] == i) add(c0, s[v], f02 .get(i + 1)), check(v, r1[i]) ;
if(p1[v] == i && p2[v] == i) add(c0, s[v], f012.get(i + 1)) ;
v = r1[i];
if(p0[v] > i && p2[v] > i) add(c1, s[v], f1 .get(i + 1)), check(v, r0[i]), check(v, r2[i]);
if(p0[v] == i && p2[v] > i) add(c1, s[v], f10 .get(i + 1)), check(v, r2[i]);
if(p0[v] > i && p2[v] == i) add(c1, s[v], f12 .get(i + 1)), check(v, r0[i]) ;
if(p0[v] == i && p2[v] == i) add(c1, s[v], f102.get(i + 1)) ;
v = r2[i];
if(p0[v] > i && p1[v] > i) add(c2, s[v], f2 .get(i + 1)), check(v, r0[i]), check(v, r1[i]);
if(p0[v] == i && p1[v] > i) add(c2, s[v], f20 .get(i + 1)), check(v, r1[i]);
if(p0[v] > i && p1[v] == i) add(c2, s[v], f21 .get(i + 1)), check(v, r0[i]) ;
if(p0[v] == i && p1[v] == i) add(c2, s[v], f201.get(i + 1)) ;
v = r0[i];
b0 = p1[v] >= i;
b1 = p2[v] >= i;
f0.add(p[v]);
if(b0) f01.add(p[v]);
if(b1) f02.add(p[v]);
if(b0 && b1) f012.add(p[v]);
v = r1[i];
b0 = p0[v] > i;
b1 = p2[v] >= i;
f1.add(p[v]);
if(b0) f10.add(p[v]);
if(b1) f12.add(p[v]);
if(b0 && b1) f102.add(p[v]);
v = r2[i];
b0 = p0[v] > i;
b1 = p1[v] > i;
f2.add(p[v]);
if(b0) f20.add(p[v]);
if(b1) f21.add(p[v]);
if(b0 && b1) f201.add(p[v]);
}
for(const pii &P : f) {
int i, j;
tie(i, j) = P;
typedef tuple<int, int, int> ti;
ti z {n, n, 0};
p0[i] < p0[j]
? umin(z, ti{p0[i], p0[j], 1})
: umin(z, ti{p0[j], p0[i], 0});
p1[i] < p1[j]
? umin(z, ti{p1[i], p1[j], 3})
: umin(z, ti{p1[j], p1[i], 2});
p2[i] < p2[j]
? umin(z, ti{p2[i], p2[j], 5})
: umin(z, ti{p2[j], p2[i], 4});
int fi, se, th;
tie(fi, se, th) = z;
if((th & 1) && fi < n)
add(th > 1 ? th > 3 ? c2 : c1 : c0, s[i], 1);
}
cout << c0 _ c1 _ c2 << '\n';
for(int i = 0; i < n; ++i) cout << s[i] << ' ';
cout << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
876 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
876 KB |
Output is correct |
| 5 |
Correct |
45 ms |
6212 KB |
Output is correct |
| 6 |
Correct |
73 ms |
8684 KB |
Output is correct |
| 7 |
Correct |
101 ms |
11628 KB |
Output is correct |
| 8 |
Correct |
136 ms |
14316 KB |
Output is correct |
| 9 |
Partially correct |
132 ms |
11372 KB |
Partially correct |
| 10 |
Partially correct |
70 ms |
9708 KB |
Partially correct |
