Submission #1143117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143117		ag_1204	Mosaic (IOI24_mosaic)	C++20	5 / 100	1093 ms	31656 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back

vi mosaic(vector<signed> X,vector<signed> Y,vector<signed> T,vector<signed> B,vector<signed> L,vector<signed> R) {
  int n=size(X),q=size(T);
  if (n==1) {
    vi C(q,X[0]);
    return C;
  } else if (n==2) {
    int grid[2][2];
    grid[0][0]=X[0]; grid[0][1]=X[1];
    grid[1][0]=Y[1]; grid[1][1]=(1-X[1])&(1-Y[1]);
    vi C(q);
    for (int k=0;k<q;k++) {
      C[k]=0;
      int a=T[k],b=B[k],c=L[k],d=R[k];
      for (int i=a;i<=b;i++) {
        for (int j=c;j<=d;j++) C[k]+=grid[i][j];
      }
    }
    return C;
  }
  vi layer0,layer1,layer2;
  for (int i=n-1;i>0;i--) layer0.pb(Y[i]);
  for (int i=0;i<n;i++) layer0.pb(X[i]);
  vector<signed> X1,Y1;
  X1.pb(Y[1]);
  for (int i=1;i<n;i++) X1.pb((1-X[i])&(1-X1[i-1]));
  Y1.pb(X[1]);
  for (int i=1;i<n;i++) Y1.pb((1-Y[i])&(1-Y1[i-1]));
  for (int i=n-1;i>1;i--) layer1.pb(Y1[i]);
  for (int i=1;i<n;i++) layer1.pb(X1[i]);
  vector<signed> X2,Y2;
  X2.pb(Y1[2]);
  for (int i=2;i<n;i++) X2.pb((1-X1[i])&(1-X2[i-2]));
  Y2.pb(X1[2]);
  for (int i=2;i<n;i++) Y2.pb((1-Y1[i])&(1-Y2[i-2]));
  for (int i=n-2;i>1;i--) layer2.pb(Y2[i]);
  for (int i=1;i<n-1;i++) layer2.pb(X2[i]);
  /*
  for (auto x:layer0) cout<<x<<" ";
  cout<<endl;
  for (auto x:layer1) cout<<x<<" ";
  cout<<endl;
  for (auto x:layer2) cout<<x<<" ";
  cout<<endl;
  */
  vi pre0(2*n),pre1(2*n-2);
  pre0[0]=0; pre1[0]=0;
  for (int i=0;i<2*n-1;i++) pre0[i+1]=pre0[i]+layer0[i];
  for (int i=0;i<2*n-3;i++) pre1[i+1]=pre1[i]+layer1[i];
  vi C(q);
  for (int k=0;k<q;k++) {
    C[k]=0;
    int a=T[k],b=B[k],c=L[k],d=R[k];
    if (a==0 || c==0) {
      int x0,y0;
      if (a>0) {
        x0=n-b; y0=n-a;
      } else if (c>0) {
        x0=n+c; y0=n+d;
      } else {
        x0=n-b; y0=n+d;
      }
      //cout<<x0<<" "<<y0<<endl;
      C[k]+=pre0[y0]-pre0[x0-1];
      //cout<<C[k]<<endl;
    }
    if ((a<=1 && b>=1) || (c<=1 && d>=1)) {
      int x1,y1;
      if (a>1) {
        x1=n-b; y1=n-a;
      } else if (c>1) {
        x1=n+c-2; y1=n+d-2;
      } else {
        x1=n-b; y1=n+d-2;
      }
      //cout<<x1<<" "<<y1<<endl;
      C[k]+=pre1[y1]-pre1[x1-1];
      //cout<<C[k]<<endl;
    }
    if (b>=2 || d>=2) {
      a=max(a,(int)2); c=max(c,(int)2);
      int xad=a-min(a-2,d-2),yad=d-min(a-2,d-2),xbc=b-min(b-2,c-2),ybc=c-min(b-2,c-2);
      //cout<<xad<<" "<<yad<<" "<<xbc<<" "<<ybc<<endl;
      int xx,yy;
      if (xad==2) xx=n+yad-5;
      else xx=n-xad-1;
      if (xbc==2) yy=n+ybc-5;
      else yy=n-xbc-1;
      if (xx>yy) swap(xx,yy);
      int l=yy-xx+1;
      //cout<<xx<<" "<<yy<<endl;
      for (int i=xx;i<=yy;i++) {
        C[k]+=min(i-xx+1,yy-i+1)*layer2[i];
        //cout<<min(i-xx+1,yy-i+1)<<endl;
      }
      //cout<<C[k]<<endl;
    }
  }
	return C;
	
	//O(n*q) solution
}

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