Submission #1214970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214970		thelegendary08	Mosaic (IOI24_mosaic)	C++17	70 / 100	317 ms	400356 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
int upslope(vi &ps, vi &abc, int l, int r){
	return (abc[r + 1] - abc[l]) - l * (ps[r + 1] - ps[l]);
}
int downslope(vi &ps, vi &cba, int l, int r){
	return cba[r + 1] - cba[l] - (ps.size() - 1 - r) * (ps[r+1] - ps[l]);
}
int solve(int l, int r, int u, int d, int n, vi &ps, vi &abc, vi &cba){
	int st = l - d + n - 3;
	int N = r - l + 1; 
	int M = d - u + 1;
	int en = st + N + M - 2;
	int len = min(N, M) - 1;
	// dout2(st,en);
	// out(len);
	// vout(ps);
	return upslope(ps, abc, st, st + len - 1) + downslope(ps, cba, en - len + 1, en) + (ps[en - len + 1] - ps[st + len]) * (len + 1);
}
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) {
	int N = X.size();
	signed Q = (signed)T.size();
	std::vector<long long> ans(Q, 0);
	//N <= 5000
	if(N <= 5000){
		vvi grid(N, vi(N));
		f0r(i, N)grid[0][i] = X[i]; 
		f0r(i, N)grid[i][0] = Y[i];
		FOR(i, 1, N){
			FOR(j, 1, N){
				if(grid[i-1][j] == 0 && grid[i][j-1] == 0)grid[i][j] = 1;
				else grid[i][j] = 0;
			}
		}
		vvi ps(N + 1, vi(N + 1));
		FOR(i, 1, N+1){
			FOR(j, 1, N+1){
				ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + grid[i-1][j-1];
			}
		}
		
		f0r(i, Q){
			ans[i] = ps[B[i] + 1][R[i] + 1] - ps[B[i] + 1][L[i]] - ps[T[i]][R[i] + 1] + ps[T[i]][L[i]];
		}
	}
	else{
		vvi rows(3, vi(N));
		f0r(i,N)rows[0][i] = X[i];
		rows[1][0] = Y[1]; 
		rows[2][0] = Y[2];
		FOR(i, 1, 3){
			FOR(j, 1, N){
				if(rows[i-1][j] == 0 && rows[i][j-1] == 0)rows[i][j] = 1;
				else rows[i][j] = 0;
			}
		}
		vvi psr(4, vi(N+1));
		FOR(i, 1, 4){
			FOR(j, 1, N+1){
				psr[i][j] = psr[i][j-1] + psr[i-1][j] - psr[i-1][j-1] + rows[i-1][j-1];
			}
		}
		vvi cols(N, vi(3));
		f0r(i, N)cols[i][0] = Y[i];
		cols[0][1] = X[1]; cols[0][2] = X[2];
		FOR(i, 1, N){
			FOR(j, 1, 3){
				if(cols[i-1][j] == 0 && cols[i][j-1] == 0)cols[i][j] = 1;
				else cols[i][j] = 0;
			}
		}
		vvi psc(N+1, vi(4));
		FOR(i, 1, N+1){
			FOR(j, 1, 4){
				psc[i][j] = psc[i-1][j] + psc[i][j-1] - psc[i-1][j-1] + cols[i-1][j-1];
			}
		}
		vi v;
		for(int i = N-1; i>=2; i--){
			v.pb(cols[i][2]);
		}
		FOR(i, 3, N){
			v.pb(rows[2][i]);
		}
		int M = v.size();
		vi ps(M + 1);
		FOR(i, 1, M+1){
			ps[i] = ps[i-1] + v[i-1];
		}
		vi abc(M+1);
		FOR(i, 1, M+1){
			abc[i] = abc[i-1] + v[i-1] * i;
		}
		vi cba(M+1);
		FOR(i, 1, M+1){
			cba[i] = cba[i-1] + v[i-1] * (M + 1 - i);
		}
		
		f0r(i, Q){
			 if(B[i] <= 2){
			 	ans[i] = psr[B[i] + 1][R[i] + 1] - psr[B[i] + 1][L[i]] - psr[T[i]][R[i] + 1] + psr[T[i]][L[i]];
			 }
			 else if(R[i] <= 2){
			 	ans[i] = psc[B[i] + 1][R[i] + 1] - psc[B[i] + 1][L[i]] - psc[T[i]][R[i] + 1] + psc[T[i]][L[i]];
			 }
			 else if(L[i] <= 1 && T[i] <= 1){
			 	int cur; 
			 	if(L[i] == 0 && T[i] == 0){
			 		cur = psr[2][R[i] + 1] + psc[B[i] + 1][2] - psr[2][2];
			 	}
			 	else if(L[i] == 1 && T[i] == 1){
			 		int rw = psr[2][R[i] + 1] - psr[1][R[i] + 1] - psr[2][L[i]] + psr[1][1];
			 		int cl = psc[B[i] + 1][2] - psc[B[i] + 1][1] - psc[T[i]][2] + psc[1][1];
			 		cur = rw + cl - rows[1][1];
			 	}
			 	else if(L[i] == 1 && T[i] == 0){
			 		int rw = psr[2][R[i] + 1] - psr[2][1];
			 		int cl = psc[B[i] + 1][2] - psc[B[i] + 1][1];
			 		cur = rw + cl - rows[0][1] - rows[1][1];
			 	}
			 	else{
			 		int rw = psr[2][R[i] + 1] - psr[1][R[i] + 1];
			 		int cl = psc[B[i] + 1][2] - psc[1][2];
			 		cur = rw + cl - rows[1][0] - rows[1][1];
			 	}
			 	// dout(cur);
			 	ans[i] = cur + solve(2, R[i], 2, B[i], N, ps, abc, cba);
			 }
			 else if(L[i] <= 1){
			 	int cur = psc[B[i] + 1][2] - psc[T[i]][2] - psc[B[i] + 1][L[i]] + psc[T[i]][L[i]];
			 	ans[i] = cur + solve(2, R[i], T[i], B[i], N, ps, abc, cba);
			 }
			 else if(T[i] <= 1){
			 	int cur = psr[2][R[i] + 1] - psr[T[i]][R[i] + 1] - psr[2][L[i]] - psr[T[i]][L[i]];
			 	ans[i] = cur + solve(L[i], R[i], 2, B[i], N, ps, abc, cba);
			 }
			 else{
			 	ans[i] = solve(L[i], R[i], T[i], B[i], N, ps, abc, cba);
			 }
		}
	}
	return ans;
}

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