Submission #1262727

#TimeUsernameProblemLanguageResultExecution timeMemory
1262727nerrrmin모자이크 (IOI24_mosaic)C++20
53 / 100
354 ms93344 KiB
#include "mosaic.h" #define pb push_back #include <vector> #include<bits/stdc++.h> using namespace std; const long long maxn = 400005; //pref[maxn][maxn]; long long n; vector < long long > a[maxn]; vector < long long > arr, state; map < long long, long long > pos; vector < long long > pref, suff; vector < long long > pp, ss; int colpref[maxn][3], rowpref[maxn][3]; long long getprefsum(long long l, long long r) /// 1 2 3 4 5 { if(r < l)return 0; long long sz = r - l + 1; long long sum = pp[r] - pp[l-1] - pref[l-1] * sz; return sum; } long long getsuffsum(long long l, long long r) { if(r < l)return 0; long long sz = r - l + 1; long long sum = ss[l] - ss[r+1] - suff[r+1] * sz; return sum; } long long getsum(long long l, long long r) { if(r < l)return 0; return pref[r] - pref[l-1]; } 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 <= 3; ++ 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 (int col = 1; col <= 2; ++ col) { for (int i = 1 ; i <= n; ++ i) colpref[i][col] = colpref[i-1][col] + a[i][col]; } for (int row = 1; row <= 2; ++ row) { for (int i = 1; i <= n; ++ i) rowpref[i][row] = rowpref[i-1][row] + a[row][i]; } vector < long long > hor, ver; arr.pb(0); state.pb(0); for (long long i = n; i >= 3; -- i) { arr.pb(a[i][3]); state.pb(i - 3); } for (long long j = 4; j <= n; ++ j) { arr.pb(a[3][j]); state.pb(3 - j); } arr.pb(0); state.pb(0); pref.resize(2*n+2, 0); suff.resize(2*n+2, 0); long long sz = arr.size()-1; for (long long i = 1; i < arr.size()-1; ++ i) pref[i] = pref[i-1] + arr[i]; for (long long i = arr.size()-2; i >= 1; -- i) suff[i] = suff[i+1] + arr[i]; pp.resize(2*n+2, 0); ss.resize(2*n+2, 0); for (long long i = 1; i < sz; ++ i) pp[i] = pp[i-1] + pref[i]; for (long long i = sz-1; i >= 1; -- i) ss[i] = ss[i+1] + suff[i]; for (long long i = 1; i < arr.size()-1; ++ i) { //cout << arr[i] << " "; pos[state[i]] = i; // cout << state[i] << " " << i << endl; } /* cout << endl; cout << "state " << endl; for (long long i = 0; i < state.size(); ++ i) cout << state[i] << " "; cout << endl; cout << "hsdiehduie " << endl; cout << "pos " << endl; for (long long i = 1; i < arr.size()-1; ++ i) { cout << state[i] << "is " << i << endl; }*/ /* cout << endl; cout << "****" << endl; cout << "pref " << endl; for (auto x: pref) cout << x << " "; cout << endl; for (auto x: pp) cout << x << " "; cout << endl; cout << "****" << endl; cout << "suff" << endl; for (auto x: suff) cout << x << " "; cout << endl; for (auto x: ss) cout << x << " "; cout << endl; cout << endl;*/ q = (long long)T.size(); vector < long long > res; for (long long i = 0; i < q; ++ i) { long long t = T[i] + 1; long long b = B[i] + 1; long long l = L[i] + 1; long long r = R[i] + 1; long long ans = 0; for (int j = t; j <= min(1LL * 2, b); ++ j) { ans += rowpref[r][j] - rowpref[l-1][j]; } if(t < 3)t = min(1LL * 2, b) + 1; if(b < t) { res.pb(ans); continue; } for (int j = l; j <= min(1LL * 2, r); ++ j) { ans += colpref[b][j] - colpref[t-1][j]; } if(l < 3)l = min(1LL * 2, r) + 1; if(l > r) { res.pb(ans); continue; } long long szh = r - l + 1; long long szv = b - t + 1; if(szh > szv) { if(szv > 1) { long long stateh0 = pos[b - l]; long long stateh1 = pos[b - (l + szv - 2)]; /// rastat ans += getsuffsum(stateh0, stateh1); } long long const0 = pos[b - (l + szv - 1)]; long long const1 = pos[b - r]; /// shte e konst long long mult = szv; if(szv > 1) { long long up0 = pos[(b-1) - r]; long long up1 = pos[t - r]; ans += getprefsum(up0, up1); } ans += getsum(const0, const1) * mult; res.pb(ans); } else { if(szh > 1) { long long stateh0 = pos[b - l]; long long stateh1 = pos[b - (r-1)]; /// rastat ans += getsuffsum(stateh0, stateh1); } long long const0 = pos[b - r]; long long const1 = pos[(t + szh - 1) - r]; /// shte e konst long long mult = szh; if(szh > 1) { long long up0 = pos[(t + szh) - r]; long long up1 = pos[t - r]; ans += getprefsum(up0, up1); } ans += getsum(const0, const1) * mult; res.pb(ans); } } // cout << res.size() << endl; return res; } /** 4 1 0 1 0 1 1 0 1 2 0 0 3 3 2 2 3 3 8 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 3 4 4 4 4 2 2 5 5 0 0 1 1 */
#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...