Submission #1283565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283565		Rares	Mosaic (IOI24_mosaic)	C++20	53 / 100	86 ms	31912 KiB

mosaic

#include <bits/stdc++.h>
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/

typedef long long ll;
const int MAXN=400010;

vector <ll> rez;

int n,q,l[MAXN],c[MAXN],l2[MAXN],c2[MAXN],l3[MAXN],c3[MAXN];
int sl1[MAXN],sl2[MAXN],sc1[MAXN],sc2[MAXN];
//int a[5000][5000];
int d[MAXN],s[MAXN],s1[MAXN],s2[MAXN];

struct query{
    int x1,y1,x2,y2;
    ll s;
}v[MAXN];

int f (int x1, int y1, int x2, int y2){
    if (x1==x2 and y1==y2) return d[x1-y1+n-2];

    int d1=x1-y2+n-2,d2=x2-y1+n-2;
    int crt=min (x2-x1,y2-y1);
    if (crt==0) return s[d2]-s[d1-1];
    ll rez=0;
    rez+=s1[d1+crt-1]-s1[d1-1]-(s[d1+crt-1]-s[d1-1])*(d1-1);
    int cf=max (x2-x1,y2-y1)-crt+1;
    rez+=cf*(s[d2-crt]-s[d1+crt-1])*(crt+1);

    rez+=s2[d2-crt+1]-s2[d2+1]-(s[d2]-s[d2-crt])*(2*n-5-d2);
    return rez;
}

void solve (){

    /**for (int i=1;i<=n;++i){
        a[1][i]=l[i];

    }

    for (int i=1;i<=n;++i){
        a[i][1]=c[i];
    }
    for (int i=2;i<=n;++i){
        for (int j=2;j<=n;++j){
            if (a[i][j-1]==a[i-1][j] and a[i][j-1]==0) a[i][j]=1;
            else a[i][j]=0;

        }

    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            cout <<a[i][j]<<' ';
        }
        cout <<'\n';
    }**/


    l2[1]=c[2];

    for (int i=2;i<=n;++i){
        if (l2[i-1]==l[i] and l[i]==0) l2[i]=1;
        else l2[i]=0;

    }

    c2[1]=l[2];

    for (int i=2;i<=n;++i){
        if (c2[i-1]==c[i] and c[i]==0) c2[i]=1;
        else c2[i]=0;
    }
    for (int i=1;i<=n;++i){
        sl1[i]=sl1[i-1]+l[i];
        sl2[i]=sl2[i-1]+l2[i];
        sc1[i]=sc1[i-1]+c[i];
        sc2[i]=sc2[i-1]+c2[i];

    }

    for (int i=1;i<=q;++i){
        if (v[i].x1==1){
            v[i].s+=sl1[v[i].y2]-sl1[v[i].y1-1];
            v[i].x1++;
        }

        if (v[i].x1==2 and v[i].x1<=v[i].x2){
            v[i].s+=sl2[v[i].y2]-sl2[v[i].y1-1];
            v[i].x1++;
        }

        if (v[i].y1==1){
            v[i].s+=sc1[v[i].x2]-sc1[v[i].x1-1];
            v[i].y1++;
        }
        if (v[i].y1==2 and v[i].y1<=v[i].y2){
            v[i].s+=sc2[v[i].x2]-sc2[v[i].x1-1];
            v[i].y1++;
        }
    }

    if (l2[3]==c2[3] and l2[3]==0) l3[3]=1;
    else l3[3]=0;

    for (int i=4;i<=n;++i){
        if (l3[i-1]==l2[i] and l2[i]==0) l3[i]=1;
        else l3[i]=0;
    }

    if (l2[3]==c2[3] and c2[3]==0) c3[3]=1;
    else c3[3]=0;

    for (int i=4;i<=n;++i){
        if (c3[i-1]==c2[i] and c2[i]==0) c3[i]=1;
        else c3[i]=0;
    }

    for (int i=3;i<=n;++i){
        d[3-i+n-2]=l3[i];
    }
    for (int i=4;i<=n;++i){
        d[i-3+n-2]=c3[i];
    }

    for (int i=1;i<=2*n-5;++i){
        s[i]=s[i-1]+d[i];
        s1[i]=s1[i-1]+i*d[i];
    }
    for (int i=2*n-5;i>=1;--i){
        s2[i]=s2[i+1]+(2*n-5-i+1)*d[i];
    }

    for (int i=1;i<=q;++i){
        if (v[i].x1>v[i].x2) continue;
        if (v[i].y1>v[i].y2) continue;
        v[i].s+=f (v[i].x1,v[i].y1,v[i].x2,v[i].y2);
    }

    for (int i=1;i<=q;++i){
        rez.push_back (v[i].s);
    }
}

vector<ll> mosaic(vector<int> x, vector<int> y,vector<int> x1, vector<int> x2,vector<int> y1, vector<int> y2){
    n=x.size ();
    q=x1.size ();
    for (int i=0;i<n;++i){
        l[i+1]=x[i];
        c[i+1]=y[i];
    }
    for (int i=0;i<q;++i){
        x1[i]++;
        x2[i]++;
        y1[i]++;
        y2[i]++;
        v[i+1]={x1[i],y1[i],x2[i],y2[i]};
    }
    solve ();

    return rez;
}

• 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: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22