Submission #1317778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317778		spetr	Mosaic (IOI24_mosaic)	C++20	12 / 100	112 ms	48924 KiB

mosaic

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>

std::vector<long long> mosaic(
    std::vector<int> X, std::vector<int> Y,
    std::vector<int> T, std::vector<int> B,
    std::vector<int> L, std::vector<int> R){

    ll n = X.size();
    ll q = T.size();

    // 1. Příprava mřížky (beze změny)
    vll row3, col3;
    vl x1, y1;
    for (ll i = 0; i < n; i++){
        x1.push_back(X[i]);
        y1.push_back(Y[i]);
    }
    row3.push_back(x1); col3.push_back(y1);
    row3.push_back({Y[1]}); row3.push_back({Y[2]}); 
    col3.push_back({X[1]}); col3.push_back({X[2]}); 

    for (ll i = 1; i < 3; i++){
        for (ll j = 1; j < n; j++){
            ll v1 = 0; ll v2 = 0;
            if (row3[i][j-1] == 0 && row3[i-1][j] == 0) v1 = 1;
            if (col3[i][j-1] == 0 && col3[i-1][j] == 0) v2 = 1;
            row3[i].push_back(v1);
            col3[i].push_back(v2);
        }
    }

    // 2. Linearizace (beze změny)
    vl s1, s2, s3;
    for (ll i = n-1; i>=0; i--) s1.push_back(col3[0][i]);
    for (ll i = 1; i < n; i++)  s1.push_back(row3[0][i]);

    for (ll i = n-1; i>=1; i--) s2.push_back(col3[1][i]);
    for (ll i = 2; i < n; i++)  s2.push_back(row3[1][i]);

    for (ll i = n-1; i>=2; i--) s3.push_back(col3[2][i]);
    for (ll i = 3; i < n; i++)  s3.push_back(row3[2][i]);

    // 3. Prefixové součty
    // Inicializujeme s nulou na začátku pro snazší indexování (p[b] - p[a])
    vl p1 = {0}, p2 = {0}, p3 = {0};
    for (ll x : s1) p1.push_back(p1.back() + x);
    for (ll x : s2) p2.push_back(p2.back() + x);
    for (ll x : s3) p3.push_back(p3.back() + x);

    // Vážený prefix pro Layer 3: q1[i] = suma s3[k]*(k+1)
    // q2 nepotřebujeme, klesání dopočítáme matematicky
    vl q1 = {0}; 
    for (ll i = 0; i < s3.size(); i++){
        q1.push_back(q1.back() + s3[i] * (i + 1));
    }

    vl ans;
    for (ll i = 0; i < q; i++){
        ll l = L[i], r = R[i], u = T[i], d = B[i];
        ll a, b;
        ll suma = 0;

        // --- Layer 1 ---
        b = 0; a = 1e9;
        if (l == 0){ a = min(a, n-d-1); b = max(b, n-u); }
        if (u == 0){ a = min(a, n+l-1); b = max(b, n+r); }
        if (a < b) suma += p1[b] - p1[a];

        // --- Layer 2 ---
        b = 0; a = 1e9;
        if (l <= 1 && r >= 1){ a = min(a, n-d-1); b = max(b, n-max(u,1ll)); }
        if (u <= 1 && d >= 1){ a = min(a, n+max(l,1ll)-3); b = max(b, n+r-2); }
        if (a < b) suma += p2[b] - p2[a];
        
        // --- Layer 3 (ZÁSADNÍ OPRAVA) ---
        if (r >= 2 && d >= 2){ 
            ll l_in = max(2ll, (ll)l);
            ll u_in = max(2ll, (ll)u);

            // Musíme zkontrolovat, zda po oříznutí zbyl platný obdélník
            if (l_in < r && u_in < d) {
                // Tvoje výpočty hranic a a b
                ll a = l_in - 2 + (n - 1) - d;
                ll b = r - 2 + n - u_in; 
                // a = start (inclusive), b = end (exclusive)
                
                ll t = min(d - u_in, r - l_in); // tloušťka
                
                // Bod zlomu (vrchol střechy)
                // (a + b - 1) / 2 zajistí správné rozdělení pro liché i sudé délky
                ll mid = (a + b - 1) / 2;

                // Definice hranic pro jednotlivé fáze:
                
                // 1. Kde končí růst? 
                // Buď v půlce (mid), nebo když dosáhne tloušťky t (a + t - 1)
                ll end_rise = min(mid, a + t - 1);
                
                // 2. Kde začíná pokles?
                // Buď těsně za půlkou, nebo když tloušťka začne klesat z t (b - t)
                ll start_fall = max(mid + 1, b - t);

                // --- Fáze 1: RŮST (Rising) ---
                // Interval [a, end_rise]
                // Váha je (index - a + 1)
                if (a <= end_rise) {
                    // Suma i*s[i] - a*suma s[i] + suma s[i] ... zjednodušeno pomocí q1:
                    // Vzorec: (q1[R] - q1[L]) - a * (p3[R] - p3[L])
                    suma += (q1[end_rise + 1] - q1[a]);
                    suma -= (p3[end_rise + 1] - p3[a]) * a;
                }

                // --- Fáze 2: POKLES (Falling) ---
                // Interval [start_fall, b)
                // Váha je (b - index) -> to je to samé jako (b + 1) - (index + 1)
                if (start_fall < b) {
                    // Vzorec: (b+1)*Suma - VáženáSuma
                    ll range_sum = p3[b] - p3[start_fall];
                    ll range_w_sum = q1[b] - q1[start_fall];
                    suma += range_sum * (b + 1) - range_w_sum;
                }

                // --- Fáze 3: PLOŠINA (Plateau) ---
                // Interval mezi [end_rise + 1, start_fall - 1]
                // Váha je konstantní t
                if (end_rise + 1 < start_fall) {
                    suma += (p3[start_fall] - p3[end_rise + 1]) * t;
                }
            }
        }

        ans.push_back(suma);
    }
    return ans;
}

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