| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1103867 | cccc | Mosaic (IOI24_mosaic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "mosaic.h"
#define int long long
#define ld long double
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define in insert
#define arr(x) array <int, x>
#define vvec vector<vector<int>>
#define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ___ 1000 * clock() / CLOCKS_PER_SEC
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e16;
int n, q, a[N], b[N], f[7][N], g[N][7], da[N], db[N];
int color[5010][5010], s[5050][5050];
int cal(int x, int y)
{
if(x == 0 && y == 0) return 1;
return 0;
}
int get(int u, int v)
{
if(u <= 5) return f[u][v];
if(v <= 5) return g[u][v];
int ans = f[5][v] + g[u][5] - f[5][5];
u -= 5; v -= 5;
if(v > u) return ans + db[u] + da[v] - da[v - u];
return ans + db[u] + da[v] - db[u - v];
}
void PRE(vector <int> &X, vector <int> &Y)
{
f(i, 0, n - 1) color[1][i + 1] = X[i], color[i + 1][1] = Y[i];
f(i, 2, n) f(j, 2, n) color[i][j] = cal(color[i - 1][j], color[i][j - 1]);
f(i, 1, n)
f(j, 1, n) cerr << color[i][j] << " \n"[j == n];
}
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(); q = T.size();
f(i, 0, n - 1)
a[i + 1] = X[i],
b[i + 1] = Y[i];
f(i, 0, q - 1) T[i]++, B[i]++, L[i]++, R[i]++;
//PRE(X, Y);
f(i, 1, n) f[1][i] = a[i];
f(i, 2, 5) f[i][1] = b[i];
f(i, 2, 5) f(j, 2, n) f[i][j] = cal(f[i - 1][j], f[i][j - 1]);
f(i, 1, n) g[i][1] = b[i];
f(i, 2, 5) g[1][i] = a[i];
f(i, 2, n) f(j, 2, 5) g[i][j] = cal(g[i - 1][j], g[i][j - 1]);
f(i, 5, n)
a[i - 4] = f[5][i], b[i - 4] = g[i][5];
f(i, 1, 5)
f(j, 1, n) f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
f(i, 1, n)
f(j, 1, 5) g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
n -= 4;
f(i, 1, n)
a[i] += a[i - 1], da[i] = da[i - 1] + a[i],
b[i] += b[i - 1], db[i] = db[i - 1] + b[i];
vector <int> ans(q);
f(i, 0, q - 1)
ans[i] = get(B[i], R[i]) - get(B[i], L[i] - 1) - get(T[i] - 1, R[i]) + get(T[i] - 1, L[i] - 1);
return ans;
}
//void SOLVE()
//{
// string s; cin >> s;
// cin >> n;
// vector <int> x(n), y(n);
// f(i, 0, n - 1) cin >> x[i];
// f(i, 0, n - 1) cin >> y[i];
// cin >> q;
// vector <int> T(q), B(q), L(q), R(q);
// f(i, 0, q - 1) cin >> T[i] >> B[i] >> L[i] >> R[i];
// vector <int> ans = mosaic(x, y, T, B, L, R);
// cout << "Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9\nOK\n";
// for(auto x : ans) cout << x << "\n";
//}
//signed main()
//{
// Keiiiii
// if(fopen("TASK.INP", "r"))
// {
// freopen("TASK.INP", "r", stdin);
// freopen("TASK.OUT", "w", stdout);
// }
// #define TASK "C"
// if(fopen(TASK ".INP", "r"))
// {
// freopen(TASK ".INP", "r", stdin);
// freopen(TASK ".OUT", "w", stdout);
// }
// int TEST = 1;
// while(TEST--)
// {
// SOLVE();
// }
// cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
// return 0;
//}
///// /\_/\
///// (= ._.)
///// / > \>