Submission #1171944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171944		LaMatematica14	Mosaic (IOI24_mosaic)	C++20	100 / 100	101 ms	36492 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;

vector<long long> mosaic(vector<int> X,  vector<int> Y, vector<int> T,  vector<int> B, vector<int> L,  vector<int> R) {
    int N = X.size();
    vector<int> fr(N), sr(N), tr(N);
    vector<int> fc(N), sc(N), tc(N);
    fr = X;
    fc = Y;

    sr[0] = fc[1];
    for (int i = 1; i < N; i++) sr[i] = !(fr[i]||sr[i-1]);
    tr[0] = fc[2];
    for (int i = 1; i < N; i++) tr[i] = !(sr[i]||tr[i-1]);

    sc[0] = fr[1];
    for (int i = 1; i < N; i++) sc[i] = !(fc[i]||sc[i-1]);
    tc[0] = fr[2];
    for (int i = 1; i < N; i++) tc[i] = !(sc[i]||tc[i-1]);

    vector<int> diag(2*N);
    int a = 0;
    for (int i = N-1; i > 2; i--) diag[a++] = tc[i]; 
    for (int i = 2; i < N; i++) diag[a++] = tr[i];

    auto prefixa = [&](vector<int> &a, vector<long long> &p) {
        p.resize(a.size()+1);
        p[0] = 0;
        for (int i = 0; i < a.size(); i++) p[i+1] = p[i]+a[i];
    };
    vector<long long> pfr, pfc, psr, psc, pdiag, psali, pscendi;
    vector<int> sali(2*N), scendi(2*N);
    for (int i = 0; i < 2*N; i++) sali[i] = diag[i]*(i+1);
    for (int i = 0; i < 2*N; i++) scendi[i] = diag[i]*((2*N-5)-i);
    prefixa(fr, pfr); prefixa(fc, pfc); prefixa(sr, psr); prefixa(sc, psc); prefixa(diag, pdiag); prefixa(sali, psali); prefixa(scendi, pscendi);
    
    int M = T.size();
    vector<long long> ans(M, 0);
    for (int i = 0; i < M; i++) {
        if (T[i] == 0) {
            ans[i] += pfr[R[i]+1]-pfr[L[i]];
            T[i]++;
            if (B[i] == 0) continue;
        }
        if (T[i] == 1) {
            ans[i] += psr[R[i]+1]-psr[L[i]];
            T[i]++;
            if (B[i] == 1) continue;
        }
        if (L[i] == 0) {
            ans[i] += pfc[B[i]+1]-pfc[T[i]];
            L[i]++;
            if (R[i] == 0) continue;
        } 
        if (L[i] == 1) {
            ans[i] += psc[B[i]+1]-psc[T[i]];
            L[i]++;
            if (R[i] == 1) continue;
        }
        // da {T[i], L[i]} a {B[i], R[i]} e' un parallelogramma 
        int di = L[i]-T[i]+N-3, df = R[i]-B[i]+N-3;
        if (df >= di) {
            ans[i] += (pdiag[df+1]-pdiag[di])*(B[i]-T[i]+1);
            // da {B[i], L[i]} a {T[i], L[i]} sale
            di = L[i]-B[i]+N-3; df = L[i]-T[i]+N-3;
            ans[i] += psali[df]-psali[di];
            ans[i] -= (di)*(pdiag[df]-pdiag[di]);
            // da {B[i], R[i]} a {T[i], R[i]} scende
            di = R[i]-B[i]+N-3; df = R[i]-T[i]+N-3;
            ans[i] += pscendi[df+1]-pscendi[di+1];
            ans[i] -= (2*N-6-df)*(pdiag[df+1]-pdiag[di+1]);
        }
        else {
            ans[i] += (pdiag[di+1]-pdiag[df])*(R[i]-L[i]+1);
            // da {B[i], L[i]} a {B[i], R[i]} sale
            di = L[i]-B[i]+N-3; df = R[i]-B[i]+N-3;
            ans[i] += psali[df]-psali[di];
            ans[i] -= (di)*(pdiag[df]-pdiag[di]);
            // da {T[i], L[i]} a {T[i], R[i]} scende
            di = L[i]-T[i]+N-3; df = R[i]-T[i]+N-3;
            ans[i] += pscendi[df+1]-pscendi[di+1];
            ans[i] -= (2*N-6-df)*(pdiag[df+1]-pdiag[di+1]);
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 22 / 22