Submission #484926

#	Time	Username	Problem	Language	Result	Execution time	Memory
484926		Kirill22	Tenis (COCI20_tenis)	C++17	110 / 110	149 ms	63028 KiB

tenis

#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] << " ";
    }
}

• Subtask 1: 35 / 35
• Subtask 2: 15 / 15
• Subtask 3: 60 / 60