Submission #1202994

#TimeUsernameProblemLanguageResultExecution timeMemory
1202994tamyteMosaic (IOI24_mosaic)C++20
22 / 100
1010 ms2162688 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) { int Q = (int)T.size(); int N = (int)X.size(); vector<vector<int>> grid(N, vector<int>(N)); for (int i = 0; i < N; ++i) { grid[0][i] = X[i]; grid[i][0] = Y[i]; } for (int i = 1; i < N; ++i) { for (int j = 1; j < N; ++j) { if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1; else grid[i][j] = 0; } } /*for (auto& v : grid) { for (auto& u : v) { cout << u << " "; } cout << "\n"; } cout << "\n";*/ vector<vector<int>> dp(N, vector<int>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { dp[i][j] = grid[i][j]; if (i > 0) dp[i][j] += dp[i - 1][j]; if (j > 0) dp[i][j] += dp[i][j - 1]; if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1]; } } std::vector<long long> C(Q, 0); for (int i = 0; i < Q; ++i) { int y1 = T[i]; int y2 = B[i]; int x1 = L[i]; int x2 = R[i]; int res = 0; if (y1 > 0) res -= dp[y1 - 1][x2]; if (x1 > 0) res -= dp[y2][x1 - 1]; if (x1 > 0 && y1 > 0) res += dp[y1 - 1][x1 - 1]; res += dp[y2][x2]; C[i] = res; } return C; } /* 4 1 0 1 0 1 1 0 1 2 0 3 0 3 2 3 0 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...