Submission #1267453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267453		vietbachleonkroos2326	Mosaic (IOI24_mosaic)	C++20	100 / 100	147 ms	58388 KiB

mosaic

#include<bits/stdc++.h>
#define TIME (1.0* clock()/CLOCKS_PER_SEC)
#define pb push_back
#define eb emplace_back
#define id1 (id<<1)
#define id2 (id<<1)|1
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>> 
#define vl vector<long long>
#define vll vector <pair<ll,ll>>
#define li pair<long long,int>
#define vil vector <pair<int,ll>>
#define db double
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <=(b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)
#define ALL(x) (x).begin(),(x).end()
#define pq priority_queue <li, vector <li>, greater <li>> 
using namespace std;
const int maxn=1e6;
//const int MOD=1e9+7;
//const int MOD=998244353;
//const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};

vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R){
    int n = (int)X.size();
    vector<vector<ll>> a(n+1), b(n+1);

    
    a[0].resize(n+1);
    b[0].resize(n+1); 

    for (int i = 1; i <= n; ++i) a[i].resize(4);
    for (int i = 1; i <= 3 && i <= n; ++i) a[i].resize(n+1);

    for (int j = 1; j <= n; ++j) a[1][j] = X[j-1];
    for (int i = 1; i <= n; ++i) a[i][1] = Y[i-1];

    for (int i = 2; i <= n; ++i){
        for (int j = 2; j < (int)a[i].size(); ++j){
            if (!a[i][j-1] && !a[i-1][j]) a[i][j] = 1;
            else a[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; ++i){
        b[i].resize(a[i].size());
        for (int j = 1; j < (int)a[i].size(); ++j){
            ll up = (i-1 >= 0 && j < (int)b[i-1].size()) ? b[i-1][j] : 0;
            ll left = (j-1 >= 0) ? b[i][j-1] : 0;
            ll upleft = (i-1 >= 0 && j-1 >= 0 && j-1 < (int)b[i-1].size()) ? b[i-1][j-1] : 0;
            b[i][j] = a[i][j] + up + left - upleft;
        }
    }

    
    vector<ll> c0(n+2, 0), c1(n+2, 0), d0(n+2, 0), d1(n+2, 0);
    if (n >= 3){
        for (int j = 3; j <= n; ++j){
            c0[j] = c0[j-1] + ( (3 < (int)a.size() && j < (int)a[3].size()) ? a[3][j] : 0 );
            c1[j] = c1[j-1] + ( (3 < (int)a.size() && j < (int)a[3].size()) ? a[3][j] * (ll)(n+1-j) : 0 );
        }
    }
    for (int i = 4; i <= n; ++i){
        d0[i] = d0[i-1] + ( (i < (int)a.size() && 3 < (int)a[i].size()) ? a[i][3] : 0 );
        d1[i] = d1[i-1] + ( (i < (int)a.size() && 3 < (int)a[i].size()) ? a[i][3] * (ll)(n+1-i) : 0 );
    }

    
    auto calc = [&](int x, int y)->ll{
        if (x <= 0 || y <= 0) return 0; 
        if (x <= 3 || y <= 3){
           
            if (x < (int)b.size() && y < (int)b[x].size()) return b[x][y];
            
            int xx = min(x, (int)b.size()-1);
            int yy = min(y, (int)b[xx].size()-1);
            if (xx >= 0 && yy >= 0) return b[xx][yy];
            return 0;
        }

        ll ret = 0;
        
        ll b_x3 = (x < (int)b.size() && 3 < (int)b[x].size()) ? b[x][3] : 0;
        ll b_3y = (3 < (int)b.size() && y < (int)b[3].size()) ? b[3][y] : 0;
        ll b_33 = (3 < (int)b.size() && 3 < (int)b[3].size()) ? b[3][3] : 0;
        ret = b_x3 + b_3y - b_33;

        if (x <= y){
           
            ll term1 = (x < (int)d1.size()) ? d1[x] : 0;
            ll term0 = (x < (int)d0.size()) ? d0[x] : 0;
            ret += term1 - term0 * (ll)(n+1-x);

            ll termc1 = (y < (int)c1.size()) ? c1[y] : 0;
            ll termc0 = (y < (int)c0.size()) ? c0[y] : 0;
            ret += termc1 - termc0 * (ll)(n+1-y);

            int idx = y - x + 2;
            ll t1 = (idx >= 0 && idx < (int)c1.size()) ? c1[idx] : 0;
            ll t0 = (idx >= 0 && idx < (int)c0.size()) ? c0[idx] : 0;
            ret -= t1 - t0 * (ll)(n+1-y);

            ret += t0 * (ll)(x-3);
        } else {
            ll termc1 = (y < (int)c1.size()) ? c1[y] : 0;
            ll termc0 = (y < (int)c0.size()) ? c0[y] : 0;
            ret += termc1 - termc0 * (ll)(n+1-y);

            ll term1 = (x < (int)d1.size()) ? d1[x] : 0;
            ll term0 = (x < (int)d0.size()) ? d0[x] : 0;
            ret += term1 - term0 * (ll)(n+1-x);

            int idx = x - y + 2;
            ll t1 = (idx >= 0 && idx < (int)d1.size()) ? d1[idx] : 0;
            ll t0 = (idx >= 0 && idx < (int)d0.size()) ? d0[idx] : 0;
            ret -= t1 - t0 * (ll)(n+1-x);

            ret += t0 * (ll)(y-3);
        }

        return ret;
    };

    vector<ll> ans;
    int Q = (int)T.size();
    ans.reserve(Q);
    for (int i = 0; i < Q; ++i){
        int lx = T[i] + 1, rx = B[i] + 1;
        int ly = L[i] + 1, ry = R[i] + 1;
        ll val = calc(rx, ry) - calc(lx-1, ry) - calc(rx, ly-1) + calc(lx-1, ly-1);
        ans.push_back(val);
    }
    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