Submission #1238689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238689		ricardsjansons	Mosaic (IOI24_mosaic)	C++20	48 / 100	84 ms	15944 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=2e5+5;

int n,pd[N*2]{},px[2][N];

int f(int i,int j){
    int x=min(i,j);
    x-=2;
    i-=x;
    j-=x;
    return n-i-1+j;
}

ll cnt(int i,int l,int r){
    int d=f(i,l);
    return pd[d+r-l]-pd[d-1];
}

int getpx(int i,int l,int r){
    return px[i][r]-(l?px[i][l-1]:0);
}

vector<long long>mosaic(vector<int>x,vector<int>y,
                        vector<int>t,vector<int>b,
                        vector<int>l,vector<int>r){
    n=x.size();
    int q=t.size();
    for(int i=0;i<n;i++){
        px[0][i]=x[i];
        if(i){
            px[0][i]+=px[0][i-1];
        }
    }
    vector<int>x1(n),y1(n);
    if(n>1){
        px[1][0]=x1[0]=y[1];
        for(int i=1;i<n;i++){
            px[1][i]=x1[i]=(x1[i-1]==0&&x[i]==0);
            px[1][i]+=px[1][i-1];
        }
        y1[0]=x[1];
        for(int i=1;i<n;i++){
            y1[i]=(y1[i-1]==0&&y[i]==0);
        }
    }
    if(n>2){
        int prv=y1[2];
        for(int i=2;i<n;i++){
            pd[f(2,i)]=prv=(prv==0&&x1[i]==0);
        }
        prv=x1[2];
        for(int i=2;i<n;i++){
            pd[f(i,2)]=prv=(prv==0&&y1[i]==0);
        }
        for(int i=1;i<=n*2;i++){
            pd[i]+=pd[i-1];
        }
    }
    vector<ll>c(q, 0);
    for(int i=0;i<q;i++){
        if(t[i]==0){
            c[i]=getpx(0,l[i],r[i]);
            continue;
        }
        if(t[i]==1){
            c[i]=getpx(1,l[i],r[i]);
            continue;
        }
        if(l[i]==0){
            c[i]+=y[t[i]];
            l[i]++;
        }
        if(l[i]==1&&l[i]<=r[i]){
            c[i]+=y1[t[i]];
            l[i]++;
        }
        if(l[i]<=r[i]){
            c[i]+=cnt(t[i],l[i],r[i]);
        }
    }
    return c;
}

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