Submission #1240712

#TimeUsernameProblemLanguageResultExecution timeMemory
1240712madamadam3Mosaic (IOI24_mosaic)C++20
22 / 100
1168 ms2114732 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; using vi =vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pi = pair<int, int>; using vpi = vector<pi>; #ifdef LOCAL #define dout std::cout #else #define dout if (0) std::cout #endif #define pb push_back #define lb lower_bound #define ub upper_bound #define all(x) (x).begin(), (x).end() #define en(x) (x).end() #define bg(x) (x).begin() #define rev(x) reverse(all(x)) #define sz(x) int((x).size()) #define FOR(i, a, b) for (int i = a; i < b; i++) #define each(a, x) for (auto &a : x) #define trace(x) for (auto &el : x) dout << el << " " vl mosaic(vi X, vi Y, vi T, vi B, vi L, vi R) { int Q = sz(T), n = sz(X); vl C(Q, 0); vvi grid(n, vi(n, 0)); FOR(i, 0, n) { grid[0][i] = X[i]; grid[i][0] = Y[i]; } FOR(i, 1, n) { FOR(j, 1, n) { if (grid[i-1][j] == 0 && grid[i][j-1] == 0) grid[i][j] = 1; else grid[i][j] = 0; } } vvl pref(n+1, vl(n+1, 0)); FOR(i, 0, n) { FOR(j, 0, n) { pref[i+1][j+1] = grid[i][j] + pref[i+1][j]; } FOR(j, 0, n) { pref[i+1][j+1] += pref[i][j+1]; } } // vl prefx(n+1, 0); FOR(i, 0, n) prefx[i+1] = prefx[i] + X[i]; FOR(qn, 0, Q) { int x1 = T[qn], x2 = B[qn], y1 = L[qn], y2 = R[qn]; // C[qn] = prefx[y2+1] - prefx[y1]; C[qn] += pref[x2+1][y2+1]; C[qn] += pref[x1][y1]; C[qn] -= pref[x1][y2+1]; C[qn] -= pref[x2+1][y1]; } return C; }
#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...