Submission #1192126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192126		NotLinux	Mosaic (IOI24_mosaic)	C++20	100 / 100	135 ms	42740 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
    int n = sz(X);
    if(n == 1){
        int k = sz(T);
        vector<long long>cevap(k);
        for(int i = 0;i<k;i++){
            cevap[i] = X[0];
        }
        return cevap;
    }
    else if(n == 2){
        int k = sz(T);
        vector<long long>cevap(k);
        int grid[2][2];
        grid[0][0] = X[0];
        grid[0][1] = X[1];
        grid[1][0] = Y[1];
        grid[1][1] = !grid[0][1] and !grid[1][0];
        // cout << grid[0][0] << " " << grid[0][1] << endl;
        // cout << grid[1][0] << " " << grid[1][1] << endl;
        for(int i = 0;i<k;i++){
            for(int j = T[i];j<=B[i];j++){
                for(int j2 = L[i];j2<=R[i];j2++){
                    cevap[i] += grid[j][j2];
                }
            }
        }
        return cevap;
    }
    vector<vector<int>>grid(n);
    grid[0] = vector<int>(n);
    grid[1] = vector<int>(n);
    grid[2] = vector<int>(n);
    for(int i = 3;i<n;i++){
        grid[i] = vector<int>(3);
    }
    for(int i = 0;i<n;i++){
        grid[0][i] = X[i];
        grid[i][0] = Y[i];
    }
    // cout << "flag0" << endl;
    // ilk iki satiri simule et ve prefix sum yap
    vector<int> presat(n);
    presat[0] = Y[2];
    for(int i = 1;i<n;i++){
        grid[1][i] = !grid[1][i-1] and !grid[0][i];
        grid[2][i] = !grid[2][i-1] and !grid[1][i];
        presat[i] = grid[2][i] + presat[i-1];
    }
    vector<long long>presat2(n);// n n-1 n-2 ile carpilmis presum
    presat2[0] = grid[2][0] * n;
    for(int i = 1;i<n;i++){
        presat2[i] = presat2[i-1] + grid[2][i] * (n - i);
    }
    // cout << "flag1" << endl;
    // ilk iki sutunu simule et ve prefix sum yap
    vector<int> presut(n);
    presut[0] = X[2];
    for(int i = 1;i<n;i++){
        grid[i][1] = !grid[i-1][1] and !grid[i][0];
        grid[i][2] = !grid[i-1][2] and !grid[i][1];
        presut[i] = grid[i][2] + presut[i-1];
    }
    vector<long long>presut2(n);// n n-1 n-2 ile carpilmis presum
    presut2[0] = grid[0][2] * n;
    for(int i = 1;i<n;i++){
        presut2[i] = presut2[i-1] + grid[i][2] * (n - i);
    }
    // gridi pref sumla
    vector<vector<int>>gridsum = grid;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<sz(grid[i]);j++){
            if(i)gridsum[i][j] += gridsum[i-1][j];
            if(j)gridsum[i][j] += gridsum[i][j-1];
            if(i and j)gridsum[i][j] -= gridsum[i-1][j-1];
        }
    }
    auto getsum = [&](int x , int y){
        if(x < 0 or y < 0)return 0ll;
        // cout << "getsum : " << x << " " << y << endl;
        long long ret = 0;
        // ilk sutun ve satir
        ret += gridsum[min(x,1)][y];
        ret += gridsum[x][min(y,1)];
        ret -= gridsum[min(x,1)][min(y,1)];
        // cout << "ret1 : " << ret << endl;
        if(x > 1 and y > 1){
            // satir
            {
                int diff = max(0 , y - x);
                long long term1 = presat2[y] - presat2[diff+1];
                long long term2 = (long long)(presat[y] - presat[diff+1]) * (long long)(n - y - 1);
                ret += term1 - term2;
                // cout << "term1 - term2 : " << term1 - term2 << endl;
                long long term3 = (long long)(presat[diff+1] - presat[1]) * (long long)(min(x,y) - 1);
                ret += term3;
                // cout << "term3 : " << term3 << endl;
                // cout << "ret2 : " << ret << endl;
            }
            // sutun
            {
                int diff = max(0 , x - y);
                long long term1 = presut2[x] - presut2[diff+1];
                long long term2 = (long long)(presut[x] - presut[diff+1]) * (long long)(n - x - 1);
                ret += term1 - term2;
                long long term3 = (long long)(presut[diff+1] - presut[1]) * (long long)(min(x,y) - 1);
                ret += term3;
                // cout << "ret3 : " << ret << endl;
            }
            ret -= (long long)grid[2][2] * (long long)(min(x,y) - 1);
        }
        // cout << "ret : " << ret << endl;
        return ret;
    };
    auto getrect = [&](int lx , int rx , int ly , int ry){
        return getsum(rx,ry) - getsum(lx-1,ry) - getsum(rx,ly-1) + getsum(lx-1,ly-1);
    };
    int k = sz(T);
    vector<long long>cevap(k);
    for(int i = 0;i<k;i++){
        cevap[i] = getrect(T[i] , B[i] , L[i] , R[i]);
    }
    return cevap;
}

• 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