#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
struct segTree{
long long *st;
long long n;
segTree(long long siz){
long long x= ceil(log2(siz));
x++;
n=siz-1;
st=new long long[(1<<x)];
fill(st,st+(1<<x),0);
}
void rupdate(long long l, long long r, long long ind, long long i, long long val){
if(i<l||i>r)
return;
if(l==r){
st[ind]=val;
return;
}
long long mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i,val);
rupdate(mid+1,r,ind*2+2,i,val);
st[ind]=st[ind*2+1]+st[ind*2+2];
}
void update(long long i, long long val){
rupdate(0,n,0,i,val);
}
long long rquery(long long l, long long r, long long s, long long e, long long ind){
if(e<l||s>r)
return 0;
if(s<=l&&r<=e){
return st[ind];
}
long long mid = (l+r)/2;
return rquery(l,mid,s,e,ind*2+1)+rquery(mid+1,r,s,e,ind*2+2);
}
long long query(long long l, long long r){
if(l>r)
return 0;
return rquery(0,n,l,r,0);
}
};
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
long long n = X.size();
long long q = (long long)T.size();
if(n==1){
vector<long long>ans(q,X[0]);
return ans;
}
else if(n==2){
long long rem = 0;
if(X[1]==Y[1]&&X[1]==0){
rem=1;
}
vector<long long>ans(q);
for(long long i = 0;i<q;i++){
//later
if(T[i]==0){
if(L[i]==0){
ans[i]+=X[0];
}
if(R[i]==1){
ans[i]+=X[1];
}
}
if(B[i]==1){
if(L[i]==0){
ans[i]+=Y[1];
}
if(R[i]==1){
ans[i]+=rem;
}
}
}
return ans;
}
//X is row top
vector<long long>nxc1(n-1);
vector<long long>nxc2(n-2);
vector<long long>nxr1(n-1);
vector<long long>nxr2(n-2);
nxc1[0]=nxr1[0]=((bool)(X[1]==0&&Y[1]==0));
for(long long i = 1;i<n-1;i++){
nxc1[i]=((bool)nxc1[i-1]==0&&Y[i+1]==0);
nxr1[i]=((bool)nxr1[i-1]==0&&X[i+1]==0);
}
nxc2[0]=nxr2[0]=((bool)(nxc1[1]==0&&nxr1[1]==0));
for(long long i = 1;i<n-2;i++){
nxc2[i]=((bool)nxc2[i-1]==0&&nxc1[i+1]==0);
nxr2[i]=((bool)nxr2[i-1]==0&&nxr1[i+1]==0);
}
long long off = n+5;
segTree up(3*n);
segTree flat(3*n);
segTree down(3*n);
set<int>ks;
for(long long i = 0;i<n-2;i++){
if(nxc2[i]){
long long k = 2-(2+i);
long long offd = k+off;
ks.insert(k);
//cout << "adding1: " << k << "\n";
//cout << "offd: " << offd << "\n";
up.update(offd,offd);
flat.update(offd,1);
down.update(offd,-offd);
}
if(nxr2[i]){
long long k = (i+2)-2;
long long offd = k+off;
ks.insert(k);
//cout << "adding2: " << k << "\n";
//cout << "offd: " << offd << "\n";
up.update(offd,offd);
flat.update(offd,1);
down.update(offd,-offd);
}
}
//segs made
vector<long long>ans(q);
for(long long i = 0;i<q;i++){
long long curr=0;
long long t,bo,l,r;
bo=T[i];
t=B[i];
l=L[i];
r=R[i];
//external:
assert(bo==t);
assert(l==r);
if(bo==1&&l){
ans[i]=nxr1[l-1];
}
else if(bo==0){
ans[i]=X[l];
}
else if(l==1){
ans[i]=nxc1[t-1];
}
else if(l==0){
ans[i]=Y[t];
}
else{
ans[i]=(bool)(ks.find(l-t)!=ks.end());
}
continue;
if(bo<2){
if(t>=2){
if(r-1>=0)
curr+=nxr1[r-1];
if(l-2>=0)
curr-=nxr1[l-2];
}
if(bo<1){
if(r>=0)
curr+=X[r];
if(l-1>=0)
curr-=X[l-1];
}
}
//cout << "part1: " << curr << "\n";
if(l<2){
if(r>=2){
if(t-1>=0){
curr+=nxc1[t-1];
curr-=nxc1[max(0LL,bo-2)];
}
}
//cout << "part2.1: " << curr << "\n";
if(l<1){
if(t>=0){
curr+=Y[t];
curr-=Y[max(0LL,bo-1)];
}
}
}
//within range:
bo=max(2LL,bo);
l=max(2LL,l);
if(r<l||t<bo){
ans[i]=curr;
continue;
}
//cout << "coords: " << l << " " << r << " " << bo << " " << t << "\n";
long long a = l-t+off;
long long b = min(r-t,l-bo)+off;
long long c = max(r-t,l-bo)+off;
long long d = r-bo+off;
if(c<b){
//swap(c,b);
assert(0);
}
//cout << a << " " << b << " " << c << " " << d << "\n";
//cout << "pre: " << curr << "\n";
curr+=up.query(a,b)-flat.query(a,b)*(a-1);
//cout << "here1: " << curr << "\n";
curr+=flat.query(b+1,c)*(min(r-l+1,t-bo+1));
//cout << "here2: " << curr << "\n";
curr+=-down.query(c+1,d)-(1LL*(c)*flat.query(c+1,d));
//cout << "segs: " << curr << "\n";
//cout << bo << " " << t << " " << l << " " << r << " " << curr << "\n";
ans[i]=curr;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |