Submission #1259271

#TimeUsernameProblemLanguageResultExecution timeMemory
1259271nerrrminMosaic (IOI24_mosaic)C++20
0 / 100
90 ms44356 KiB
#include "mosaic.h" #define pb push_back #include <vector> #include<bits/stdc++.h> using namespace std; const long long maxn = 200005; //pref[maxn][maxn]; long long n; vector < long long > a[maxn]; long long pref[6][maxn]; long long prefy[maxn]; 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) { long long q = (long long)T.size(); std::vector<long long> C(q, 0); n = X.size(); a[0].resize(n+1, 0); a[1].resize(n+1, 0); a[2].resize(n+1, 0); a[3].resize(n+1, 0); a[4].resize(n+1, 0); for (long long j = 5; j <= n; ++ j) a[j].resize(6, 0); for (long long i = 1; i <= n; ++ i) a[1][i] = X[i-1]; for (long long i = 1; i <= n; ++ i) a[i][1] = Y[i-1]; for (long long i = 2; i <= 4; ++ i) { for (long long j = i; j <= n; ++ j) { if(!a[i-1][j] && !a[i][j-1])a[i][j] = 1; else a[i][j] = 0; } for (long long j = i; j <= n; ++ j) { if(!a[j-1][i] && !a[j][i-1])a[j][i] = 1; else a[j][i] = 0; } } for (long long i = 1; i < 5; ++ i) { for (long long j = 1; j <= n; ++ j) pref[i][j] = pref[i][j-1] + a[i][j]; } prefy[1] = a[4][4]; for (long long i = 2; i <= n; ++ i) prefy[i] = prefy[i-1] + a[i+3][4]; q = (long long)T.size(); //std::vector<long long> C(q, 0); vector < long long > res; for (long long i = 0; i < q; ++ i) { long long row = T[i] + 1; long long l = L[i] + 1; long long r = R[i] + 1; long long col = l; long long ans = 0; if(row <= 4) { res.pb(pref[row][r] - pref[row][l-1]); continue; } if(col < 4) { for (long long j = l; j < min(1LL * 4, r+1); ++ j) ans += a[row][j]; col = 4; } if(col > r) { res.pb(ans); continue; } l = col; long long pl = max(l, row); long long pr = r; long long start_point = (pl - row) + 1; long long sz = pr - pl + 1; long long end_point = start_point + sz - 1; if(start_point <= end_point) ans += pref[4][end_point] - pref[4][start_point-1]; r = min(r, row - 1); /// l to r v prefy if(l <= r) { long long st = (row - l) + 1; long long ed = 2; ans += prefy[st] - prefy[ed-1]; } res.pb(ans); } return res; } /** 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...