Submission #1199661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199661		ansori	Mosaic (IOI24_mosaic)	C++20	100 / 100	101 ms	23932 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int s = 2;
const bool stres = 0;
int n , q;
vector<ll> suf , sufi , prei , vec;
int get(int x , int y , int n){
	return 0;
}
int f(int x , int y) { return ((x == 0) and (y == 0)); }
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
	n = x.size();
	if(n < s + 1){
		for(int i = n;i < s + 1; ++ i) x.push_back(0) , y.push_back(0);
		n = s + 1;
	}
	if(stres){
	    vector<vector<bool>> val(n , vector<bool> (n , 0));
	    for(int i = 0;i < n; ++ i){
	    	for(int j = 0;j < n; ++ j){
	    		if(i == 0) val[i][j] = x[j];
	    		else if(j == 0) val[i][j] = y[i];
	    		else val[i][j] = ((val[i - 1][j] == 0) & (val[i][j - 1] == 0));
	    		cout << val[i][j] << ' ';
	    	}
	    	cout << '\n';
	    }
    }
	q = t.size();
	//cout << q << ' ';
    vector<ll> ans(q , 0);
    for(int c = 0;c < s; ++ c){
    	vec = {} , suf = vector<ll> (2 * n , 0);
    	//for(auto to : x) cout << to << ' ';
    	//cout << '\n';
    	//for(auto to : y) cout << to << ' ';
    	//cout << '\n';
		for(int i = y.size() - 1; i >= 0; -- i) vec.push_back(y[i]);
		for(int i = 1;i < x.size(); ++ i) vec.push_back(x[i]);
		for(int i = 0;i < vec.size(); ++ i) suf[i + 1] = suf[i] + vec[i]; 
 		for(int i = 0;i < q; ++ i){
			if(t[i] <= b[i] and l[i] <= r[i]){
	 			if(t[i] == 0){
	 				ans[i] += suf[r[i] + n] - suf[l[i] + n - 1];
	 			}
	 			if(l[i] == 0){
	 				ans[i] += suf[n - t[i]] - suf[n - b[i] - 1];
	 			}
	 			if(l[i] == 0 and t[i] == 0) ans[i] -= vec[n - 1];
	 			t[i] = max(0 , t[i] - 1);
	 			b[i] --;
	 			l[i] = max(0 , l[i] - 1);
	 			r[i] --;
 			}
 		}
 		vector<int> nx , ny;
 		nx.push_back(f(x[1] , y[1]));
 		ny.push_back(f(x[1] , y[1]));
 		for(int i = 2;i < x.size(); ++ i) nx.push_back(f(nx.back() , x[i]));
 		for(int i = 2;i < y.size(); ++ i) ny.push_back(f(ny.back() , y[i]));
 		x = nx;
 		y = ny;
 		n --;
    }
    vec = {} , suf = vector<ll> (2 * n , 0);
	for(int i = y.size() - 1; i >= 0; -- i) vec.push_back(y[i]);
	for(int i = 1;i < x.size(); ++ i) vec.push_back(x[i]);
	for(int i = 0;i < vec.size(); ++ i) suf[i + 1] = suf[i] + vec[i]; 
    sufi = prei = vector<ll> (2 * n + 1 , 0);
    sufi[0] = 0;
    for(int i = 1;i < 2 * n; ++ i){
		sufi[i] = sufi[i - 1] + 1ll * vec[i - 1] * i;
    }
    prei[2 * n - 1] = 0;
    for(int i = 2 * n - 2; i >= 0; -- i){
    	prei[i] = prei[i + 1] + 1ll * vec[i] * (2 * n - 1 - i);
    }
    for(int i = 0;i < q; ++ i){
    	if(t[i] <= b[i] and l[i] <= r[i]){
    		ll l1 = n - 1 - b[i] + l[i] , r1 = n - 1 - t[i] + r[i];
    		l1 ++ , r1 ++;
    		ll x = min(b[i] - t[i] + 1 , r[i] - l[i] + 1);
    		ll r2 = l1 + x - 2;
    		ll l2 = r1 - x + 2;
    		//cout << ans[i] << ' ' << l1 << ' ' << r2 << ' ' << l2 << ' ' << r1 << ' ';
    		if(l1 <= r2){
  				ans[i] += 1ll * (sufi[r2] - sufi[l1 - 1]) - (l1 - 1) * (suf[r2] - suf[l1 - 1]);
  				//cout << ans[i] << ' ';
  				ans[i] += 1ll * (prei[l2 - 1] - prei[r1]) - (2 * n - 1 - r1) * (suf[r1] - suf[l2 - 1]);
  				//cout << ans[i] << ' ';
    		}
    		ans[i] += 1ll * x * (suf[l2 - 1] - suf[r2]);
			//cout << '\n';
    	}
    }
    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