#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int q,n;
vector<vector<int>> lft;
vector<vector<int>> top;
vector<int> dia;
// X cest le top
// Y cest la gauche
// [le x][le y]
int todia(int x, int y){
return (n-x-1)+y;
}
std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y, std::vector<signed> T, std::vector<signed> B,std::vector<signed> L, std::vector<signed> R) {
q = sz(T); n=sz(Y);
lft.resize(3,vector<int>(n,0));
top.resize(n,vector<int>(3,0));
dia.resize(n+n+4,0);
for (int i = 0; i < n; i++)
{
lft[0][i]=Y[i];
top[i][0]=X[i];
}
if(n>1){
lft[1][0]=X[1];
top[0][1]=Y[1];
if(n>2){
lft[2][0]=X[2];
top[0][2]=Y[2];
}
}
for (int i = 1; i < n&&n>1; i++)
{
top[i][1]=(top[i-1][1]==0&&top[i][0]==0);
lft[1][i]=(lft[1][i-1]==0&&lft[0][i]==0);
}
for (int i = 1; i < n&&n>2; i++)
{
top[i][2]=(top[i-1][2]==0&&top[i][1]==0);
lft[2][i]=(lft[2][i-1]==0&&lft[1][i]==0);
dia[todia(i,2)]=top[i][2];
dia[todia(2,i)]=lft[2][i];
}
vector<vector<int>> fullgrid(n,vector<int>(n,0));
vector<vector<int>> fakegrid(n,vector<int>(n,0));
vector<vector<int>> prefix(n,vector<int>(n,0));
for (int i = 0; i < n; i++){
for (int j = 0; j < min(n,3LL); j++)
{
fullgrid[i][j]=top[i][j];
fullgrid[j][i]=lft[j][i];
}
}
for (int i = 0; i < n; i++)
{
fakegrid[i][0]=X[i];
fakegrid[0][i]=Y[i];
}
for (int i = 1; i < n; i++){
for (int j = 1; j < n; j++)
{
fakegrid[i][j]=(fakegrid[i-1][j]==0&&fakegrid[i][j-1]==0);
}
}
for (int i = 3; i < n; i++){
for (int j = 3; j < n; j++)
{
fullgrid[i][j]=dia[todia(i,j)];
fullgrid[j][i]=dia[todia(j,i)];
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
{
prefix[i][j]=fullgrid[i][j];
if(i>0) prefix[i][j]+=prefix[i-1][j];
if(j>0) prefix[i][j]+=prefix[i][j-1];
if(i>0&&j>0) prefix[i][j]-=prefix[i-1][j-1];
//cerr << fullgrid[j][i] << " ";
}
//cerr << "\n";
}
//cerr<<"\n";
/*for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
{
//cerr << fakegrid[j][i] << " ";
if(fakegrid[j][i]!=fullgrid[j][i]) cerr << "ERROR - " << i << " " << j << "\n";
assert(fakegrid[j][i]==fullgrid[j][i]);
}
//cerr << "\n";
}*/
std::vector<long long> C(q, 0);
for (int i = 0; i < q; i++)
{
int l=L[i],r=R[i],t=T[i],b=B[i];
int sm=prefix[r][b];
if(l>0) sm-=prefix[l-1][b];
if(t>0) sm-=prefix[r][t-1];
if(l>0&&t>0) sm+=prefix[l-1][t-1];
C[i]=sm;
}
return C;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
2 ms |
1360 KB |
Output is correct |
12 |
Correct |
2 ms |
1360 KB |
Output is correct |
13 |
Correct |
3 ms |
1360 KB |
Output is correct |
14 |
Correct |
2 ms |
1360 KB |
Output is correct |
15 |
Correct |
1 ms |
592 KB |
Output is correct |
16 |
Correct |
1 ms |
592 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1141 ms |
1537372 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
2 ms |
1360 KB |
Output is correct |
12 |
Correct |
2 ms |
1360 KB |
Output is correct |
13 |
Correct |
3 ms |
1360 KB |
Output is correct |
14 |
Correct |
2 ms |
1360 KB |
Output is correct |
15 |
Correct |
1 ms |
592 KB |
Output is correct |
16 |
Correct |
1 ms |
592 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
18 |
Correct |
709 ms |
599880 KB |
Output is correct |
19 |
Correct |
748 ms |
599984 KB |
Output is correct |
20 |
Correct |
751 ms |
599860 KB |
Output is correct |
21 |
Correct |
663 ms |
599780 KB |
Output is correct |
22 |
Correct |
738 ms |
599948 KB |
Output is correct |
23 |
Correct |
152 ms |
102984 KB |
Output is correct |
24 |
Correct |
148 ms |
103236 KB |
Output is correct |
25 |
Correct |
142 ms |
103120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
9076 KB |
Output is correct |
2 |
Execution timed out |
1167 ms |
1640984 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1192 ms |
1654500 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1141 ms |
1537372 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
2 ms |
1360 KB |
Output is correct |
13 |
Correct |
2 ms |
1360 KB |
Output is correct |
14 |
Correct |
3 ms |
1360 KB |
Output is correct |
15 |
Correct |
2 ms |
1360 KB |
Output is correct |
16 |
Correct |
1 ms |
592 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
18 |
Correct |
1 ms |
592 KB |
Output is correct |
19 |
Execution timed out |
1141 ms |
1537372 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |