제출 #1199587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199587		ansori	Mosaic (IOI24_mosaic)	C++20	12 / 100	1095 ms	20648 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int s = 3000;
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){
		for(int i = n;i < s; ++ i) x.push_back(0) , y.push_back(0);
		n = s;
	}
	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 --;
    }
    /*
    sufi = prei = vector<ll> (2 * n + 1 , 0);
    sufi[0] = 0;
    for(int i = 1;i < 2 * n; ++ i){
		suf[i] = suf[i - 1] + vec[i - 1] * i;
    }
    prei[2 * n - 1] = 0;
    for(int i = 2 * n - 2; i >= 0; -- i){
    	prei[i] = prei[i + 1] + vec[i] * (2 * n - 1 - i);
    }
    for(int i = 0;i < q; ++ i){
    	if(t[i] <= b[i] and l[i] <= r[i]){
    		int l1 = n - 1 - b[i] + l[i] , r1 = n - 1 - t[i] + r[i];
    		l1 ++ , r1 ++;
    		int x = min(b[i] - t[i] + 1 , r[i] - l[i] + 1);
    		int r2 = l1 + x - 1;
    		int l2 = r1 - x + 1;
    		if(l1 <= r2){
  				ans[i] += (sufi[r2] - sufi[l1 - 1]) - (l1 - 1) * (suf[r2] - suf[l1 - 1]);
  				ans[i] += (prei[l2 - 1] - prei[r1]) - (r1 - 2 * n - 2) * (suf[r1] - suf[l2 - 1]);
    		}
    		ans[i] += ((b[i] - t[i] + 1) + (r[i] - l[i] + 1) - 1) * (suf[l2 - 1] - suf[r2]);
    	}
    }
    */
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 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