Submission #1213781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213781		user736482	Mosaic (IOI24_mosaic)	C++20	7 / 100	101 ms	32040 KiB

mosaic

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n;
vector<ll>pr1={0},pr2={0};
ll tb1[200007][4],tb2[4][200007];
ll zap(ll x,ll y){
    if(x<0 || y<0)return 0;
    ll ans=tb1[x][min(y,3LL)]+tb2[min(x,3LL)][y]-tb1[min(x,3LL)][min(y,3LL)];
    ll p1=n-y,p2=n-y+min(x,y),p3=x-(y-1)+n,p4=x+n;
    ans+=-(pr2[p2-1]-pr2[p1-1]-(p2-p1)*pr1[p1-1])+((pr1[p3-1]-pr1[p1-1])*(min(x,y)+1))+(pr2[p4-1]-pr2[p3-1]-(p4-p3)*pr1[p3-1]);
    return ans;
}
vector<ll>mosaic(vector<int>x,vector<int>y,vector<int>t,vector<int>b,vector<int>l,vector<int>r){
    n=x.size();
    while(n<4){
        x.pb(0);
        y.pb(0);
        n++;
    }
    for(ll i=0;i<n;i++){
        tb1[i][0]=x[i];
        tb2[0][i]=y[i];
    }
    for(ll i=1;i<4;i++){
        tb1[0][i]=y[i];
        tb2[i][0]=x[i];
        for(ll j=1;j<n;j++){
            tb1[j][i]=!(tb1[j-1][i] || tb1[j][i-1]);
            tb2[i][j]=!(tb2[i-1][j] || tb2[i][j-1]);
        }
    }
    for(ll i=0;i<3;i++)pr1.pb(0);
    for(ll i=n-1;i>3;i--)pr1.pb(pr1.back()+tb2[3][i]);
    for(ll i=3;i<n;i++)pr1.pb(pr1.back()+tb1[i][3]);
    for(ll i=0;i<3;i++)pr1.pb(pr1.back());
    for(ll i : pr1)pr2.pb(pr2.back()+i);
    pr2.erase(pr2.begin());
    for(ll i=0;i<n;i++){
        for(ll j=0;j<4;j++){
            tb1[i][j]-=pr1[i-j+n]-pr1[i-j+n-1];
            if(i)tb1[i][j]+=tb1[i-1][j];
            if(j)tb1[i][j]+=tb1[i][j-1];
            if(i && j)tb1[i][j]-=tb1[i-1][j-1];
            tb2[j][i]-=pr1[j-i+n]-pr1[j-i+n-1];
            if(i)tb2[j][i]+=tb2[j][i-1];
            if(j)tb2[j][i]+=tb2[j-1][i];
            if(i && j)tb2[j][i]-=tb2[j-1][i-1];
        }
    }
    vector<ll>ans;
    for(ll i=0;i<t.size();i++)ans.pb(zap(r[i],b[i])-zap(r[i],t[i]-1)-zap(l[i]-1,b[i])+zap(l[i]-1,t[i]-1));
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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