Submission #1104048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104048		PedroBigMan	Mosaic (IOI24_mosaic)	C++17	12 / 100	146 ms	41164 KiB

mosaic

#include "mosaic.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

vector<vector<ll> > ps_small_up, ps_small_left, ps_small;
ll X, Y;
vector<ll> psX, psY, psX_temp, psY_temp;

ll f(ll A, ll B)
{
    if(A==0 && B==0) {return 1;} else {return 0;}
}

ll PS(ll x1, ll x2, ll y1, ll y2)
{
    if(x1==0 && y1==0)
    {
        X = x2; Y = y2; ll ans = 0;
        ans -= ps_small[min(X,1LL)][min(Y,1LL)];
        ans+=ps_small_left[X][min(Y,1LL)];
        ans+=ps_small_up[min(X,1LL)][Y];
        X-=2; Y-=2;
        if(X<0 || Y<0) {return ans;}
        if(X>Y) 
        {
            ans+=(Y+1)*(psX[X-Y]-psX[0]);
            ans+=((Y+1)*psY[Y]-psY_temp[Y]);
            ans+=((X+1)*(psX[X]-psX[X-Y])-(psX_temp[X]-psX_temp[X-Y]));
        }
        else 
        {
            if(Y>X) {ans+=(X+1)*(psY[Y-X]-psY[0]);}
            ans+=((X+1)*psX[X]-psX_temp[X]);
            ans+=((Y+1)*(psY[Y]-psY[Y-X])-(psY_temp[Y]-psY_temp[Y-X]));
        }
        return ans;
    }
    else
    {
        ll ans = PS(0,x2,0,y2);
        if(x1>0) {ans-=PS(0,x1-1,0,y2);}
        if(y1>0) {ans-=PS(0,x2,0,y1-1);}
        if(x1>0 && y1>0) {ans+=PS(0,x1-1,0,y1-1);}
        return ans;
    }
}

vector<long long> mosaic(vector<int> XX, vector<int> YY, vector<int> T, vector<int> B, vector<int> L, vector<int> R) 
{
    ll N =  XX.size(); ll Q = T.size();
    if(N==1)
    {
        vector<ll> ans(Q,0); REP(q,0,Q) {ans[q]=XX[0];} return ans;
    }
    else if(N==2)
    {
        vector<vector<ll> > a(2,vector<ll>(2)); a[0][0]=XX[0]; a[0][1]=XX[1]; a[1][0]=YY[1]; a[1][1]=f(XX[1],YY[1]);
        vector<ll> ans(Q,0);
        REP(q,0,Q)
        {
            REP(i,0,2)
            {
                REP(j,0,2)
                {
                    if(i>=T[q] && i<=B[q] && j>= L[q] && j<=R[q] && a[i][j]==1) {ans[q]++;}
                }
            }
        }
        return ans;
    }

    vector<ll> X(N-2,0), Y(N-2,0);

    vector<vector<ll> > a;

    a.clear(); a= vector<vector<ll> >(3,vector<ll>(3,0)); ps_small = vector<vector<ll> >(2,vector<ll>(2,0));
    REP(i,0,3)
    {
        REP(j,0,3)
        {
            if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
            if(i==0 && j==0) {ps_small[i][j]=a[i][j];}
            else if(i==0 && j<=1) {ps_small[i][j]=ps_small[i][j-1]+a[i][j];}
            else if(j==0 && i<=1) {ps_small[i][j]=ps_small[i-1][j]+a[i][j];}
            else if(i<=1 && j<=1) {ps_small[i][j]=a[i][j]+ps_small[i-1][j]+ps_small[i][j-1]-ps_small[i-1][j-1];}
        }
    }

    X[0]=a[2][2]; Y[0]=a[2][2];

    a.clear(); a= vector<vector<ll> >(N,vector<ll>(2,0)); ps_small_left = vector<vector<ll> >(N,vector<ll>(2,0));
    REP(i,0,N)
    {
        REP(j,0,2)
        {
            if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
            if(i==0 && j==0) {ps_small_left[i][j]=a[i][j];}
            else if(i==0) {ps_small_left[i][j]=ps_small_left[i][j-1]+a[i][j];}
            else if(j==0) {ps_small_left[i][j]=ps_small_left[i-1][j]+a[i][j];}
            else {ps_small_left[i][j]=a[i][j]+ps_small_left[i-1][j]+ps_small_left[i][j-1]-ps_small_left[i-1][j-1];}
        }
    }

    REP(i,1,N-2)
    {
        X[i]=f(X[i-1],a[i+2][1]);
    }

    a.clear(); a= vector<vector<ll> >(2,vector<ll>(N,0)); ps_small_up = vector<vector<ll> >(2,vector<ll>(N,0));
    REP(i,0,2)
    {
        REP(j,0,N)
        {
            if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
            if(i==0 && j==0) {ps_small_up[i][j]=a[i][j];}
            else if(i==0) {ps_small_up[i][j]=ps_small_up[i][j-1]+a[i][j];}
            else if(j==0) {ps_small_up[i][j]=ps_small_up[i-1][j]+a[i][j];}
            else {ps_small_up[i][j]=a[i][j]+ps_small_up[i-1][j]+ps_small_up[i][j-1]-ps_small_left[i-1][j-1];}
        }
    }

    REP(i,1,N-2)
    {
        Y[i]=f(Y[i-1],a[1][i+2]);
    }

    ll cursum;

    cursum=0; REP(i,0,N-2) {cursum+=X[i]; psX.pb(cursum);}
    cursum=0; REP(i,0,N-2) {cursum+=Y[i]; psY.pb(cursum);}
    cursum=0; REP(i,0,N-2) {cursum+=(i*X[i]); psX_temp.pb(cursum);}
    cursum=0; REP(i,0,N-2) {cursum+=(i*Y[i]); psY_temp.pb(cursum);}

    vector<ll> ans(Q,0);
    REP(q,0,Q)
    {
        ans[q]=PS(T[q],B[q],L[q],R[q]);
    }
    return ans;
}

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