Submission #1129626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129626		c0det1ger	Mosaic (IOI24_mosaic)	C++20	100 / 100	425 ms	55812 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define double long double

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    if (X.size() <= 3){
        vector<vector<int>> pre(X.size() + 1, vector<int>(X.size() + 1));
        vector<vector<int>> real(X.size() + 1, vector<int>(X.size() + 1));
        for (int i = 1; i <= X.size(); i++){
            real[1][i] = X[i - 1];
            real[i][1] = Y[i - 1];
        }
        for (int i = 2; i <= X.size(); i++){
            for (int j = 2; j<= X.size(); j++){
                real[i][j] = 1 - max(real[i - 1][j], real[i][j - 1]);
            }
        }
        for (int i = 1; i <= X.size(); i++){
            for (int j = 1; j <= X.size(); j++){
                pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + real[i][j];
            }
        }
        vector<long long> ans;
        for (int i = 0; i < T.size(); i++){
            R[i]++;
            B[i]++;
            ans.push_back(pre[B[i]][R[i]] - pre[T[i]][R[i]] - pre[B[i]][L[i]] + pre[T[i]][L[i]]);
        }
        return ans;
    }
    else{
        vector<long long> ans;
        map<int, long long> mp;
        vector<int> x(X.size()), y(X.size());
        x[0] = Y[1];
        for (int i = 1; i < X.size(); i++){
            x[i] = 1 - max(X[i], x[i - 1]);
        }
        y[0] = X[1];
        for (int i = 1; i < Y.size(); i++){
            y[i] = 1 - max(Y[i], y[i - 1]);
        }
        
        vector<int> xx(X.size()), yy(X.size());
        xx[1] = y[2];
        for (int i = 2; i < X.size(); i++){
            xx[i] = 1 - max(x[i], xx[i - 1]);
        }
        yy[1] = x[2];
        for (int i = 2; i < Y.size(); i++){
            yy[i] = 1 - max(y[i], yy[i - 1]);
        }
        
        for (int i = 2; i < X.size(); i++){
            mp[i - 2] = yy[i];
            mp[-i + 2] = xx[i];
        }
        
        int sz = (int)X.size();
        vector<long long> pre(2 * sz), pre1(2 * sz), pre2(2 * sz + 1);

        mp[sz - 2] = x[sz - 1];
        mp[sz - 1] = X[sz - 1];
        mp[-sz + 2] = y[sz - 1];
        mp[-sz + 1] = Y[sz - 1];
        
        for (int i = 1; i < 2 * sz; i++){
            pre[i] = pre[i - 1] + mp[i - sz];
            pre1[i] = pre1[i - 1] + mp[i - sz] * i;
        }
        for (int i = 2 * sz - 1; i >= 1; i--){
            pre2[i] = pre2[i + 1] + mp[i - sz] * (2 * sz - i);
        }
        
        vector<long long> p1x(sz + 1), p2x(sz + 1), p1y(sz + 1), p2y(sz + 1);
        
        for (int i = 1; i <= sz; i++){
            p1x[i] = p1x[i - 1] + X[i - 1];
            p2x[i] = p2x[i - 1] + x[i - 1];
            p1y[i] = p1y[i - 1] + Y[i - 1];
            p2y[i] = p2y[i - 1] + y[i - 1];
        }
        
        for (int i = 0; i < T.size(); i++){
            long long res = 0;
            
            int t = T[i], b = B[i], l = L[i], r = R[i];
            if (t == 0){
                res += p1x[r + 1] - p1x[l];
                t++;
            }
            if (t == 1){
                res += p2x[r + 1] - p2x[l];
                t++;
            }
            if (b == 0){
                ans.push_back(p1x[r + 1] - p1x[l]);
                continue;
            }
            if (b == 1){
                ans.push_back(res);
                continue;
            }
            
            if (l == 0){
                res += p1y[b + 1] - p1y[t];
                l++;
            }
            if (r == 0){
                ans.push_back(res);
                continue;
            }
            if (l == 1){
                res += p2y[b + 1] - p2y[t];
                l++;
            }
            if (r == 1){
                ans.push_back(res);
                continue;
            }
            
            int lft1 = sz + (b - l) + 1;
            int ext1 = min((r - l) + 1, (b - t) + 1);
            int rgt1 = lft1 - ext1;
            res += pre2[rgt1] - pre2[lft1] - (pre[lft1 - 1] - pre[rgt1 - 1]) * (2 * sz - lft1);
            //cout << pre[lft1] - pre[rgt1] << "\n";
            int rgt2 = sz + (t - r) - 1;
            int lft2 = rgt2 + ext1;
            res += pre1[lft2] - pre1[rgt2] - (pre[lft2] - pre[rgt2]) * (rgt2);
            //cout << lft2 << "\n";
            res += (pre[rgt1 - 1] - pre[lft2]) * ext1;
            ans.push_back(res);
        }
        
        return ans;
    }
    return {};
}

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

• 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