| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1199666 | ansori | 모자이크 (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#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;
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();
vector<ll> ans(q , 0);
for(int c = 0;c < s; ++ c){
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];
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] + 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 - 2;
int l2 = r1 - x + 2;
if(l1 <= r2){
ans[i] += 1ll * (sufi[r2] - sufi[l1 - 1]) - (l1 - 1) * (suf[r2] - suf[l1 - 1]);
ans[i] += 1ll * (prei[l2 - 1] - prei[r1]) - (2 * n - 1 - r1) * (suf[r1] - suf[l2 - 1]);
}
ans[i] += 1ll * x * (suf[l2 - 1] - suf[r2]);
}
}
return ans;
}