제출 #1136107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136107		naneosmic	Mosaic (IOI24_mosaic)	C++20	100 / 100	966 ms	86564 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> mosaic(vector<signed> X, vector<signed> Y,vector<signed> T, vector<signed> B,vector<signed> L, vector<signed> R) {
    int Q = (int)T.size();
    vector<int> C(Q);
    int n=X.size();
    vector<vector<int>>v(max(3LL,n),vector<int>(3,0));
    if(n>=3){
        for(int i=0;i<3;i++)v[i].resize(n,0);
    }
    for(int i=0;i<n;i++)v[0][i]=X[i];
    for(int i=0;i<n;i++)v[i][0]=Y[i];
    for(int i=1;i<n;i++){
        if(v[0][i]==1LL||v[1][i-1]==1LL){
            v[1][i]=0;
        }else v[1][i]=1;
        if(v[1][i]==1LL||v[2][i-1]==1LL){
            v[2][i]=0;
        }else v[2][i]=1;
    }
    for(int i=1;i<n;i++){
        if(v[i][0]==1LL||v[i-1][1]==1LL){
            v[i][1]=0;
        }else v[i][1]=1;
        if(v[i][1]==1LL||v[i-1][2]==1LL){
            v[i][2]=0;
        }else v[i][2]=1;
    }
    vector<vector<int>>pref(6,vector<int>(n+1,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            pref[j][i+1]=pref[j][i]+v[j][i];
            pref[3+j][i+1]=pref[3+j][i]+v[i][j];
        }
    }
    map<int,int>pref1;
    map<int,int>pref2;
    if(n>=3){
        for(int i=0;i<n;i++){
            pref1[i]=0;
            pref1[-i]=0;
            pref2[i]=0;
            pref2[-i]=0;
        }
        for(int i=n-1;i>=2;i--){
            pref1[2-i]=pref1[1-i]+v[i][2];
        }
        for(int i=3;i<n;i++){
            pref1[i-2]=pref1[i-3]+v[2][i];
        }
        pref2[-(n-3)]=pref1[-(n-3)];
        for(int i=-(n-3);i<=(n-3);i++){
            pref2[i]=pref2[i-1]+pref1[i];
        }
    }
    for(int i=0;i<Q;i++){
        int modif=0;
        int x1=T[i];
        int x2=B[i];
        int y1=L[i];
        int y2=R[i];
        while(x1<2){
            if(x1>x2)break;
            modif+=(pref[x1][y2+1]-pref[x1][y1]);
            x1++;
        }
        if(x1>x2){
            C[i]=modif;
            continue;
        }
        while(y1<2){
            if(y1>y2)break;
            modif+=(pref[3+y1][x2+1]-pref[3+y1][x1]);
            y1++;
        }
        if(y1>y2){
            C[i]=modif;
            continue;
        }
        int d1=x2-x1+1;
        int d2=y2-y1+1;
        int num=y2-x1;
        int sol=pref2[num]-pref2[num-d1]-pref2[num-d2]+pref2[num-d1-d2];
        C[i]=modif+sol;
    }
    return C;
}

• 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