| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1283564 | Rares | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/
typedef long long ll;
const int MAXN=400010;
vector <ll> rez;
int n,q,l[MAXN],c[MAXN],l2[MAXN],c2[MAXN],l3[MAXN],c3[MAXN];
int sl1[MAXN],sl2[MAXN],sc1[MAXN],sc2[MAXN];
//int a[5000][5000];
int d[MAXN],s[MAXN],s1[MAXN],s2[MAXN];
struct query{
int x1,y1,x2,y2;
ll s;
}v[MAXN];
int f (int x1, int y1, int x2, int y2){
if (x1==x2 and y1==y2) return d[x1-y1+n-2];
int d1=x1-y2+n-2,d2=x2-y1+n-2;
int crt=min (x2-x1,y2-y1);
if (crt==0) return s[d2]-s[d1-1];
ll rez=0;
rez+=s1[d1+crt-1]-s1[d1-1]-(s[d1+crt-1]-s[d1-1])*(d1-1);
int cf=max (x2-x1,y2-y1)-crt+1;
rez+=cf*(s[d2-crt]-s[d1+crt-1])*(crt+1);
rez+=s2[d2-crt+1]-s2[d2+1]-(s[d2]-s[d2-crt])*(2*n-5-d2);
return rez;
}
void solve (){
/**for (int i=1;i<=n;++i){
a[1][i]=l[i];
}
for (int i=1;i<=n;++i){
a[i][1]=c[i];
}
for (int i=2;i<=n;++i){
for (int j=2;j<=n;++j){
if (a[i][j-1]==a[i-1][j] and a[i][j-1]==0) a[i][j]=1;
else a[i][j]=0;
}
}
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
cout <<a[i][j]<<' ';
}
cout <<'\n';
}**/
l2[1]=c[2];
for (int i=2;i<=n;++i){
if (l2[i-1]==l[i] and l[i]==0) l2[i]=1;
else l2[i]=0;
}
c2[1]=l[2];
for (int i=2;i<=n;++i){
if (c2[i-1]==c[i] and c[i]==0) c2[i]=1;
else c2[i]=0;
}
for (int i=1;i<=n;++i){
sl1[i]=sl1[i-1]+l[i];
sl2[i]=sl2[i-1]+l2[i];
sc1[i]=sc1[i-1]+c[i];
sc2[i]=sc2[i-1]+c2[i];
}
for (int i=1;i<=q;++i){
if (v[i].x1==1){
v[i].s+=sl1[v[i].y2]-sl1[v[i].y1-1];
v[i].x1++;
}
if (v[i].x1==2 and v[i].x1<=v[i].x2){
v[i].s+=sl2[v[i].y2]-sl2[v[i].y1-1];
v[i].x1++;
}
if (v[i].y1==1){
v[i].s+=sc1[v[i].x2]-sc1[v[i].x1-1];
v[i].y1++;
}
if (v[i].y1==2 and v[i].y1<=v[i].y2){
v[i].s+=sc2[v[i].x2]-sc2[v[i].x1-1];
v[i].y1++;
}
}
if (l2[3]==c2[3] and l2[3]==0) l3[3]=1;
else l3[3]=0;
for (int i=4;i<=n;++i){
if (l3[i-1]==l2[i] and l2[i]==0) l3[i]=1;
else l3[i]=0;
}
if (l2[3]==c2[3] and c2[3]==0) c3[3]=1;
else c3[3]=0;
for (int i=4;i<=n;++i){
if (c3[i-1]==c2[i] and c2[i]==0) c3[i]=1;
else c3[i]=0;
}
for (int i=3;i<=n;++i){
d[3-i+n-2]=l3[i];
}
for (int i=4;i<=n;++i){
d[i-3+n-2]=c3[i];
}
for (int i=1;i<=2*n-5;++i){
s[i]=s[i-1]+d[i];
s1[i]=s1[i-1]+i*d[i];
}
for (int i=2*n-5;i>=1;--i){
s2[i]=s2[i+1]+(2*n-5-i+1)*d[i];
}
for (int i=1;i<=q;++i){
if (v[i].x1>v[i].x2) continue;
if (v[i].y1>v[i].y2) continue;
v[i].s+=f (v[i].x1,v[i].y1,v[i].x2,v[i].y2);
}
for (int i=1;i<=q;++i){
rez.push_back (v[i].s);
}
}
vector<ll> mosaic(vector<int> x, vector<int> y,vector<int> x1, vector<int> x2,vector<int> y1, vector<int> y2){
n=x.size ();
q=x1.size ();
for (int i=0;i<n;++i){
l[i+1]=x[i];
c[i+1]=y[i];
}
for (int i=0;i<q;++i){
x1[i]++;
x2[i]++;
y1[i]++;
y2[i]++;
v[i+1]={x1[i],y1[i],x2[i],y2[i]};
}
solve ();
return rez;
}
signed main()
{
int n,q;
cin >>n;
vector<int> X,Y,T,B,L,R;
for (int i=1;i<=n;++i){
int x;
cin >>x;
X.push_back (x);
}
for (int i=1;i<=n;++i){
int x;
cin >>x;
Y.push_back (x);
}
cin >>q;
for (int i=1;i<=q;++i){
int x;
cin >>x;
T.push_back (x);
}
for (int i=1;i<=q;++i){
int x;
cin >>x;
B.push_back (x);
}
for (int i=1;i<=q;++i){
int x;
cin >>x;
L.push_back (x);
}
for (int i=1;i<=q;++i){
int x;
cin >>x;
R.push_back (x);
}
vector <ll> rez=mosaic (X,Y,T,B,L,R);
for (auto x:rez) cout <<x<<'\n';
return 0;
}