Submission #1305472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305472		nicknamedtwice	Mosaic (IOI24_mosaic)	C++20	100 / 100	109 ms	41152 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std; using ll=long long;
vector<ll> mosaic(
 vector<signed> X, vector<signed> Y,
 vector<signed> T, vector<signed> B,
 vector<signed> L, vector<signed> R
){
 int n=X.size(),Q=T.size(); const int K=3;
 int MID=n+6,S=MID*2+n+10;
 vector<int> vert((n+K+10)*(K+2)),horz((K+2)*(n+K+10));
 auto V=[&](int j,int i)->int&{return vert[j*(K+2)+i];};
 auto H=[&](int i,int j)->int&{return horz[i*(n+K+10)+j];};
 for(int i=0;i<n;i++) H(1,i+1)=X[i],V(i+1,1)=Y[i];
 for(int i=0;i<min(n,K);i++) H(i+1,1)=Y[i],V(1,i+1)=X[i];
 for(int i=2;i<=K+1;i++) for(int j=2;j<=n;j++) V(j,i)=!V(j-1,i)&&!V(j,i-1), H(i,j)=!H(i-1,j)&&!H(i,j-1);
 vector<ll>A(S);
 for(int i=0;i<=n;i++) A[MID+i]=H(K+1,K+1+i), A[MID-i]=V(K+1+i,K+1);
 vector<int> prv((n+2)*(K+2)), prh((K+2)*(n+2));
 auto PV=[&](int j,int i)->int&{return prv[j*(K+2)+i];};
 auto PH=[&](int i,int j)->int&{return prh[i*(n+2)+j];};
 for(int i=1;i<=K;i++)
  for(int j=1;j<=n;j++)
   PV(j,i)=PV(j-1,i)+PV(j,i-1)-PV(j-1,i-1)+V(j,i),
   PH(i,j)=PH(i-1,j)+PH(i,j-1)-PH(i-1,j-1)+H(i,j);
 vector<ll> pref(S); vector<long long> prefk(S);
 for(int i=0;i<S;i++){ pref[i]=(i?pref[i-1]:0)+A[i]; prefk[i]=(i?prefk[i-1]:0)+A[i]*(ll)i; }
 ll totalA=pref[S-1], totalAk=prefk[S-1];
 auto PR1=[&](int i)->ll{return i>=0?pref[i]:0;};
 auto PR2=[&](int i)->ll{return i>=0? (ll)(i+1)*pref[i]-prefk[i] : 0;};
 auto SF1=[&](int i)->ll{ if(i<0||i>=S) return 0; ll before=(i?pref[i-1]:0); return totalA-before; };
 auto SF2=[&](int i)->ll{
  if(i<0||i>=S) return 0;
  ll b = i?pref[i-1]:0;
  ll bk = i?prefk[i-1]:0;
  return (totalAk-bk) - (ll)(i-1)*(totalA-b);
 };
 vector<ll> res(Q);
 for(int q=0;q<Q;q++){
  int t=T[q]+1,b=B[q]+1,l=L[q]+1,r=R[q]+1;
  int pt=min(b,K);
  if(t<=K){
   res[q]+=PH(pt,r)-PH(t-1,r)-PH(pt,l-1)+PH(t-1,l-1);
   t=pt+1;
  }
  if(t>b) continue;
  int pl=min(r,K);
  if(l<=K){
   res[q]+=PV(b,pl)-PV(t-1,pl)-PV(b,l-1)+PV(t-1,l-1);
   l=pl+1;
  }
  if(l>r) continue;
  int wsz=min(r-l+1,b-t+1), s;
  int id1,id2;
  s=min(b,l); b-=s; l-=s; id1=b?MID-b:MID+l;
  s=min(t,r); t-=s; r-=s; id2=t?MID-t:MID+r;
  int j1=id1+wsz-1, j2=id2-wsz+1;
  res[q]+=(ll)wsz*(PR1(j2)-PR1(j1-1));
  j1--; j2++;
  if(j1<id1||j2>id2) continue;
  res[q]+=SF2(id1)-SF2(j1+1)-SF1(j1+1)*(j1-id1+1);
  res[q]+=PR2(id2)-PR2(j2-1)-PR1(j2-1)*(id2-j2+1);
 }
 return res;
}

• 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