Submission #1104684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104684		Nonoze	Mosaic (IOI24_mosaic)	C++17	100 / 100	209 ms	65320 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define fi first
#define se second

vector<int> diagor, diagol, diago;

int query(int l, int r) {
	if (l>r) return 0;
	if (l==0) return diago[r];
	return diago[r]-diago[l-1];
}

int queryl(int l, int r) {
	if (l>r) return 0;
	if (l==0) return diagol[r];
	int rem=l*query(l, r);
	return diagol[r]-diagol[l-1]-rem;
}

int queryr(int l, int r) {
	if (l>r) return 0;
	if (l==0) return diagor[r];
	int rem=(sz(diago)-r-1)*query(l, r);
	return diagor[r]-diagor[l-1]-rem;
}

int calc(int x, int y, int a, int b) {
	assert(x==0);
	int mn=min(a+1, b-y+1);
	int l=y-a, midl=y-a+mn-1, midr=b-mn+1, r=b;
	int ansl=queryl(l, midl-1);
	int ansr=queryr(midr+1, r);
	int ansmid=query(midl, midr)*mn;
	return ansl+ansr+ansmid;
}


int to_add, sz;

int calcq(int x, int a, int y, int b, vector<vector<int>>& line, vector<vector<int>>& column) {
	int ans=0;
	int fx=x, fy=y, fa=a, fb=b;
	cmax(fx, sz), cmax(fy, sz);
	if (fx<=fa && fy<=fb) {
		ans+=calc(0, fy-fx+to_add, fa-fx, fb-fx+to_add);
	}
	if (x<sz && b>=sz) {
		for (int i=x; i<min(a+1, sz); i++) {
			ans+=line[i][b]-line[i][max(sz-1, y-1)];
		}
	}
	if (y<sz) {
		for (int i=y; i<min(b+1, sz); i++) {
			ans+=column[a][i]-(x?column[x-1][i]:0);
		}
	}
	return ans;
}

vector<signed> x, y, t, b, l, r;
int n, q;


vector<int> mosaic(vector<signed> X, vector<signed> Y, vector<signed> T, vector<signed> B, vector<signed> L, vector<signed> R) {	
	x=X, y=Y, t=T, b=B, l=L, r=R, n=sz(x), q=sz(t);
	sz=min(5LL, n);
	vector<vector<int>> line(sz), column(n);
	for (int i=0; i<n; i++) line[0].pb(x[i]), column[i].pb(y[i]);
	for (int i=1; i<sz; i++) line[i].pb(column[i][0]), column[0].pb(line[0][i]);
	for (int i=1; i<sz; i++) {
		for (int j=1; j<n; j++) {
			if (line[i-1][j]==0 && line[i][j-1]==0) line[i].pb(1);
			else line[i].pb(0);
		}
	}
	for (int i=1; i<n; i++) {
		for (int j=1; j<sz; j++) {
			if (column[i-1][j]==0 && column[i][j-1]==0) column[i].pb(1);
			else column[i].pb(0);
		}
	}

	to_add=n-1-sz+1;
	for (int i=n-1; i>=sz; i--) diago.pb(column[i][sz-1]);
	for (int i=sz-1; i<n; i++) diago.pb(line[sz-1][i]);
	for (int i=0; i<sz; i++) {
		for (int j=1; j<n; j++) {
			line[i][j]+=line[i][j-1];
			column[j][i]+=column[j-1][i];
		}
	}
	diagor=diagol=diago;
	diagor[0]=sz(diago)*diago[0];
	for (int i=1; i<sz(diago); i++) diagol[i]=diagol[i-1]+diago[i]*(i+1);
	for (int i=1; i<sz(diago); i++) diagor[i]=diagor[i-1]+diago[i]*(sz(diago)-i);
	for (int i=1; i<sz(diago); i++) diago[i]+=diago[i-1];
	vector<int> ans;
	for (int tt=0; tt<q; tt++) {
		ans.pb(calcq(t[tt], b[tt], l[tt], r[tt], line, column));
	}
	return ans;
}

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