Submission #484926

# Submission time Handle Problem Language Result Execution time Memory
484926 2021-11-05T18:06:46 Z Kirill22 Tenis (COCI20_tenis) C++17
110 / 110
149 ms 63028 KB
#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] << " ";
    }
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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