Submission #1333541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333541		PlayVoltz	Mosaic (IOI24_mosaic)	C++20	0 / 100	1117 ms	2162688 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

vector<int> mosaic(vector<signed> X, vector<signed> Y, vector<signed> t, vector<signed> b, vector<signed> l, vector<signed> r){
	if (X.size()<=5000){
		int n=X.size();
		vector<int> ans(r.size());
		vector<vector<int> > grid(n, vector<int>(n, 0));
		for (int i=0; i<n; ++i)grid[0][i]=X[i], grid[i][0]=Y[i];
		for (int i=1; i<n; ++i)for (int j=1; j<n; ++j)if (!grid[i-1][j]&&!grid[i][j-1])grid[i][j]=1;
		for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[i][j]+=grid[i-1][j];
		for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[j][i]+=grid[j][i-1];
		for (int i=0; i<r.size(); ++i)ans[i]=grid[b[i]][r[i]]-(t[i]?grid[t[i]-1][r[i]]:0)-(l[i]?grid[b[i]][l[i]-1]:0)+2*(t[i]&&l[i]?grid[t[i]-1][l[i]-1]:0);
		return ans;
	}
}

Compilation message (stderr)

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22