Submission #1317776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317776		spetr	모자이크 (IOI24_mosaic)	C++20	5 / 100	113 ms	52028 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>>
#define pl pair<long long, long long>
#define vb vector<bool>

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, q;
    n = X.size();
    q = T.size();

    vll row3;
    vll 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);
        }
    }

    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]);
    }

    vl p1, p2, p3;
    p1 = p2 = p3 = {0};
    for (ll i = 0; i < s1.size(); i++){
        p1.push_back(s1[i] + p1[i]);
    }
    for (ll i = 0; i < s2.size(); i++){
        p2.push_back(s2[i] + p2[i]);
    }
    for (ll i = 0; i < s3.size(); i++){
        p3.push_back(s3[i] + p3[i]);
    }


    vl q1, q2;
    q1 = q2 = {0};
    for (ll i = 0; i < s3.size(); i++){
        q1.push_back(q1[i] + s3[i]*(i+1));
        q2.push_back(q2[i] + s3[s3.size()-1-i]*(i+1));
    }

    vl ans;
    for (ll i = 0; i < q; i++){
        ll l, r, u, d;
        l = L[i]; r = R[i]; u = T[i]; d = B[i];
        ll a, b;
        ll suma = 0;
        //Layer1
        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];
        }
        //Layer2
        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];
        }
        // Layer3
        if (r >= 2  || d >= 2){
            l = max(2ll, l);
            u = max(2ll, u);
            ll a = l - 2 + (n-1)-d;
            ll b = r - 2 + n - u;
            ll t = min(d-u, r-l); // thickness
            ll v = q2.size();
            //arithmetic sequence
            suma += q1[a+t] - q1[a]; // správně
            suma += q2[v-b+1] - q2[v-b-t+1];
            
            suma -= (p3[a+t] - p3[a])*a; //správně
            suma -= (p3[b] - p3[b-t])*(v-b-1);

            suma += (p3[b-t] - p3[a+t])*(t+1); //správně
        }

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

/*/int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> X {0,0,0,0,0,0,0};
    vector<int> Y {0,0,0,0,0,0,0};
    vector<int> T {2};
    vector<int> B {6};
    vector<int> L {4};
    vector<int> R {6};

    vl ans = mosaic(X, Y, T, B, L, R);
    for (auto x : ans){
        cout << x << "\n";
    }

    return 0;
}
/*/

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