#include "mosaic.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
vector<vector<ll> > ps_small_up, ps_small_left, ps_small;
ll X, Y;
vector<ll> psX, psY, psX_temp, psY_temp;
ll f(ll A, ll B)
{
if(A==0 && B==0) {return 1;} else {return 0;}
}
ll PS(ll x1, ll x2, ll y1, ll y2)
{
if(x1==0 && y1==0)
{
X = x2; Y = y2; ll ans = 0;
ans -= ps_small[min(X,1LL)][min(Y,1LL)];
ans+=ps_small_left[X][min(Y,1LL)];
ans+=ps_small_up[min(X,1LL)][Y];
X-=2; Y-=2;
if(X<0 || Y<0) {return ans;}
if(X>Y)
{
ans+=(Y+1)*(psX[X-Y]-psX[0]);
ans+=((Y+1)*psY[Y]-psY_temp[Y]);
ans+=((X+1)*(psX[X]-psX[X-Y])-(psX_temp[X]-psX_temp[X-Y]));
}
else
{
if(Y>X) {ans+=(X+1)*(psY[Y-X]-psY[0]);}
ans+=((X+1)*psX[X]-psX_temp[X]);
ans+=((Y+1)*(psY[Y]-psY[Y-X])-(psY_temp[Y]-psY_temp[Y-X]));
}
return ans;
}
else
{
ll ans = PS(0,x2,0,y2);
if(x1>0) {ans-=PS(0,x1-1,0,y2);}
if(y1>0) {ans-=PS(0,x2,0,y1-1);}
if(x1>0 && y1>0) {ans+=PS(0,x1-1,0,y1-1);}
return ans;
}
}
vector<long long> mosaic(vector<int> XX, vector<int> YY, vector<int> T, vector<int> B, vector<int> L, vector<int> R)
{
ll N = XX.size(); ll Q = T.size();
if(N==1)
{
vector<ll> ans(Q,0); REP(q,0,Q) {ans.pb(XX[0]);} return ans;
}
else if(N==2)
{
vector<vector<ll> > a(2,vector<ll>(2)); a[0][0]=XX[0]; a[0][1]=XX[1]; a[1][0]=YY[1]; a[1][1]=f(XX[1],YY[1]);
vector<ll> ans(Q,0);
REP(q,0,Q)
{
REP(i,0,2)
{
REP(j,0,2)
{
if(i>=T[q] && i<=B[q] && j>= L[q] && j<=R[q] && a[i][j]==1) {ans[q]++;}
}
}
}
return ans;
}
return vector<ll>(Q,0);
vector<ll> X(N-2,0), Y(N-2,0);
vector<vector<ll> > a;
a.clear(); a= vector<vector<ll> >(3,vector<ll>(3,0)); ps_small = vector<vector<ll> >(2,vector<ll>(2,0));
REP(i,0,3)
{
REP(j,0,3)
{
if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
if(i==0 && j==0) {ps_small[i][j]=a[i][j];}
else if(i==0 && j<=1) {ps_small[i][j]=ps_small[i][j-1]+a[i][j];}
else if(j==0 && i<=1) {ps_small[i][j]=ps_small[i-1][j]+a[i][j];}
else if(i<=1 && j<=1) {ps_small[i][j]=a[i][j]+ps_small[i-1][j]+ps_small[i][j-1]-ps_small[i-1][j-1];}
}
}
X[0]=a[2][2]; Y[0]=a[2][2];
a.clear(); a= vector<vector<ll> >(N,vector<ll>(2,0)); ps_small_left = vector<vector<ll> >(N,vector<ll>(2,0));
REP(i,0,N)
{
REP(j,0,2)
{
if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
if(i==0 && j==0) {ps_small_left[i][j]=a[i][j];}
else if(i==0) {ps_small_left[i][j]=ps_small_left[i][j-1]+a[i][j];}
else if(j==0) {ps_small_left[i][j]=ps_small_left[i-1][j]+a[i][j];}
else {ps_small_left[i][j]=a[i][j]+ps_small_left[i-1][j]+ps_small_left[i][j-1]-ps_small_left[i-1][j-1];}
}
}
REP(i,1,N-2)
{
X[i]=f(X[i-1],a[i+2][1]);
}
a.clear(); a= vector<vector<ll> >(2,vector<ll>(N,0)); ps_small_up = vector<vector<ll> >(2,vector<ll>(N,0));
REP(i,0,2)
{
REP(j,0,N)
{
if(i==0) {a[i][j]=XX[j];} else if(j==0) {a[i][j]=YY[i];} else {a[i][j]=f(a[i][j-1],a[i-1][j]);}
if(i==0 && j==0) {ps_small_up[i][j]=a[i][j];}
else if(i==0) {ps_small_up[i][j]=ps_small_up[i][j-1]+a[i][j];}
else if(j==0) {ps_small_up[i][j]=ps_small_up[i-1][j]+a[i][j];}
else {ps_small_up[i][j]=a[i][j]+ps_small_up[i-1][j]+ps_small_up[i][j-1]-ps_small_left[i-1][j-1];}
}
}
REP(i,1,N-2)
{
Y[i]=f(Y[i-1],a[1][i+2]);
}
ll cursum;
cursum=0; REP(i,0,N-2) {cursum+=X[i]; psX.pb(cursum);}
cursum=0; REP(i,0,N-2) {cursum+=Y[i]; psY.pb(cursum);}
cursum=0; REP(i,0,N-2) {cursum+=(i*X[i]); psX_temp.pb(cursum);}
cursum=0; REP(i,0,N-2) {cursum+=(i*Y[i]); psY_temp.pb(cursum);}
vector<ll> ans(Q,0);
REP(q,0,Q)
{
ans[q]=PS(T[q],B[q],L[q],R[q]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
8260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
11288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
