Submission #1244057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244057		alexander707070	Mosaic (IOI24_mosaic)	C++20	100 / 100	102 ms	33528 KiB

mosaic

#include<bits/stdc++.h>
#define MAXN 400007
using namespace std;

int n,q;
int t[5007][5007];

long long len;
int row[5][MAXN],col[5][MAXN];
int prefrow[5][MAXN],prefcol[5][MAXN];

int seq[MAXN];

long long incr[MAXN],decr[MAXN],pref[MAXN];

vector<long long> sol;

int nand(int x,int y){
    return x==0 and y==0;
}

long long diag(long long from,long long to,bool in){
    if(in)return (incr[to]-incr[from-1]) - (pref[to]-pref[from-1])*(from-1);
    else return (decr[from]-decr[to+1]) - (pref[to]-pref[from-1])*(len-to);
}

long long mult(int from,int to,long long c){
    return (pref[to]-pref[from-1])*c;
}

int ff(int diff){
    return n-diff-2;
}

long long calc(int from,int to,int l,int r){

    int sq=min(to-from+1,r-l+1);

    long long res=0;
    res+=diag(ff(to-l),ff((to-sq+1)-l),true);
    res+=diag(ff(from-(r-sq+1)),ff(from-r),false);

    if(to-from+1>sq)res+=mult( ff((to-sq)-l) , ff((from+1)-l) , sq);
    if(r-l+1>sq)res+=mult( ff(from-(l+1)) , ff(from-(r-sq)) , sq);

    if(to-from==r-l)res-=mult(ff(from-l),ff(from-l),sq);

    return res;
}

long long sum(int from,int to,int l,int r){
    if(from>=3 and l>=3)return calc(from,to,l,r);

    if(from<3 and to>=3)return sum(from,2,l,r) + sum(3,to,l,r);
    if(l<3 and r>=3)return sum(from,to,l,2) + sum(from,to,3,r);

    long long res=0;
    if(to<=2){
        res=prefrow[from][r] - prefrow[from][l-1];
        if(from<to)res+=prefrow[to][r] - prefrow[to][l-1];
    }else if(r<=2){
        res=prefcol[l][to] - prefcol[l][from-1];
        if(l<r)res+=prefcol[r][to] - prefcol[r][from-1];
    }

    return res;
}

vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R){
	n=int(X.size());
	q=int(T.size());

	for(int i=1;i<=n;i++){
        row[1][i]=X[i-1];
        col[1][i]=Y[i-1];
    }

    row[2][1]=col[1][2];
    col[2][1]=row[1][2];

    for(int i=2;i<=n;i++){
        row[2][i]=nand(row[2][i-1],row[1][i]);
        col[2][i]=nand(col[2][i-1],col[1][i]);
    }

    row[3][1]=col[1][3];
    row[3][2]=col[2][3];

    col[3][1]=row[1][3];
    col[3][2]=row[2][3];

    for(int i=3;i<=n;i++){
        row[3][i]=nand(row[3][i-1],row[2][i]);
        col[3][i]=nand(col[3][i-1],col[2][i]);
    }

    for(int i=1;i<=3;i++){
        for(int f=1;f<=n;f++){
            prefrow[i][f]=prefrow[i][f-1]+row[i][f];
            prefcol[i][f]=prefcol[i][f-1]+col[i][f];
        }
    }

    for(int i=n;i>=3;i--){
        len++;
        seq[len]=col[3][i];
    }

    for(int i=4;i<=n;i++){
        len++;
        seq[len]=row[3][i];
    }

    for(int i=1;i<=len;i++){
        pref[i]=pref[i-1]+seq[i];
        incr[i]=incr[i-1]+seq[i]*i;
    }

    for(int i=len;i>=1;i--){
        decr[i]=decr[i+1]+seq[i]*(len-i+1);
    }

    for(int i=0;i<q;i++){
        int from,to,l,r;

        from=T[i]+1; to=B[i]+1;
        l=L[i]+1; r=R[i]+1;

        sol.push_back(sum(from,to,l,r));
    }

    return sol;
}

/*int main(){

	//mosaic({1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{},{},{},{});
    auto y=mosaic({1, 0, 1, 0}, {1, 1, 0, 1}, {0, 2}, {3, 3}, {0, 0}, {3, 2});
	for(auto s:y)cout<<s<<" ";

	//auto yo=mosaic({0,0,0,0,0}, {0,0,0,0,0}, {1, 0}, {4, 3}, {2,0}, {4,3});
	//for(auto s:yo)cout<<s<<" ";

	return 0;
}*/

• 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