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 <bits/stdc++.h>
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 100100;
const int oo = 2e9;
int ok1[3][8], ok2[3][8][8];
ll win[N], crt[3];
int a[3][N], n, loc[3][N];
int MIN[8][N], nm[N];
void calc(int x, int y){
i2 mn = {oo, oo};
for (int j = 0; j < 3; j++)
mn = min(mn, {min(loc[j][x], loc[j][y]), max(loc[j][x], loc[j][y])});
for (int j = 0; j < 3; j++) {
i2 cr = {min(loc[j][x], loc[j][y]), max(loc[j][x], loc[j][y])};
if (mn == cr){
if (loc[j][x] > loc[j][y])
swap(x, y);
win[x]++;
crt[j]++;
return;
}
}
}
bool cmp(int _x, int _y){
return MIN[7][_x] > MIN[7][_y];
}
void upd_ans(int x){
int sub = 0;
for (int i = 0; i < 3; i++)
if (loc[i][x] == MIN[7][x])
sub |= (1 << i);
{
// 0
if (MIN[7][x] == loc[0][x]) {
crt[0] += ok1[0][sub];
win[x] += ok1[0][sub];
}
}
{
// 1
if (MIN[7][x] == loc[1][x]) {
crt[1] += ok2[1][sub][(1 & sub)];
win[x] += ok2[1][sub][(1 & sub)];
}
}
{
// 2
if (MIN[7][x] == loc[2][x]) {
crt[2] += ok2[2][sub][(3 & sub)];
win[x] += ok2[2][sub][(3 & sub)];
}
}
}
void insert(int x){
for (int i = 0; i < 3; i++)
for (int sub = 0; sub < 8; sub++){
ok1[i][sub] += bool(MIN[sub][x] == loc[i][x]);
for (int sb = 0; sb < 8; sb++)
if ((sb & sub) == sb)
ok2[i][sub][sb] += bool(MIN[sub][x] == loc[i][x] && MIN[sub][x] < MIN[sb][x]);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int j = 0; j < 3; j++)
for (int i = 1; i <= n; i++) {
cin >> a[j][i];
loc[j][a[j][i]] = i;
}
for (int i = 1; i <= n; i++)
for (int msk = 0; msk < 8; msk++){
int res = oo;
for (int j = 0; j < 3; j++)
if (msk & (1 << j))
res = min(res, loc[j][i]);
MIN[msk][i] = res;
nm[i] = i;
}
sort(nm + 1, nm + n + 1, cmp);
for (int i = 1; i <= n; ){
int j = i;
while (j <= n && MIN[7][nm[j]] == MIN[7][nm[i]]) {
upd_ans(nm[j]);
j++;
}
for (int i1 = i; i1 < j; i1++)
for (int I2 = i1 + 1; I2 < j; I2++)
calc(nm[i1], nm[I2]);
for (int i1 = i; i1 < j; i1++)
insert(nm[i1]);
i = j;
}
for (int i = 0; i < 3; i++)
cout << crt[i] << " ";
cout << '\n';
for (int i = 1; i <= n; i++)
cout << win[i] << " ";
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... |